Question

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root:

int height (treeptr n) {
  if (n == NULL) return -1;
  if (n->left == NULL)
    if (n->right == NULL) return 0;
    else return B1;      // Box 1
  else {
    h1 = height(n->left);
    if (n->right == NULL) return (1+h1);
    else {
      h2 = height(n->right);
      return B2;          // Box 2
    }
  }
}

The appropriate expressions for the two boxes B1 and B2 are

Accepted Answer

The correct answer is (A) B1: (1+height(n->right))   B2: (1+max(h1,h2)). Box 1 handles a node with only a right child: its height is 1 (the edge down) plus the height of the right subtree, so B1 = 1+height(n->right). Box 2 handles a node with both children: its height is 1 (the edge down) plus whichever child subtree is taller, so B2 = 1+max(h1,h2).

Explanation