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,