(Solved):Design a divide-and-conquer algorithm in pseudocode for computing the number of levels in a binary tree. In particular, your algorithm must return 0 and 1 for the empty and single-node trees, respe… View Answer…

 

Question

Design a divide-and-conquer algorithm in pseudocode for computing the number of levels in a binary tree. In particular, your algorithm must return 0 and 1 for the empty and single-node trees, respectively. What is the time efficiency class of your algorithm?

 

EXPERT ANSWER

BinaryTreeLevel(x):
     if x = nil:
          return 0
     else:
          lSubTreeLevel = BinaryTreeLevel(x.leftSubtree)
          rSubTreeLevel = BinaryTreeLevel(x.rightSubtree)
          if lSubTreeLevel > rSubTreeLevel:
                   return lSubTreeLevel + 1
          else:
                   return rSubTreeLevel + 1

Here,

in each recursive call,

Scroll to top