GATE CS 2012 Q47 — Trees

The height of a binary tree is defined as the number of edges on the longest path from the root to a leaf. By this definition:

• An empty tree (NULL) has a height of $-1$.
• A single-node tree (leaf) has a height of $0$.
• For any node $n$, its height is $1 + \max(\text{height}(n \to \text{left}), \text{height}(n \to \text{right}))$.

Let us analyze the cases in the given pseudo-code:

1. Determining Box 1 (B1)

This block is executed when n -> left == NULL but n -> right != NULL:

if(n -> left == NULL)
   if(n -> right == NULL) return 0;
   else return B1; // Box 1

Since the left child is empty and the right child exists, the height of the tree rooted at $n$ is $1$ plus the height of its right subtree. Therefore:

2. Determining Box 2 (B2)

This block is executed when both n -> left and n -> right are not NULL:

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

Here, $h1$ is the height of the left subtree and $h2$ is the height of the right subtree. Since both subtrees exist, the height of the tree at $n$ is $1$ plus the maximum of the heights of the two subtrees. Therefore:

Thus, the correct expressions are:

• B1: $(1 + \text{height}(n \to \text{right}))$
• B2: $(1 + \max(h1, h2))$