GATE CS 2012 Q.47 (CS Q.47): Binary Trees, Binary Search Trees and Balanced Trees

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode 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 /* Box 1 */ ;
    else {
        h1 = height(n->left);
        if (n->right == NULL) return (1 + h1);
        else {
            h2 = height(n->right);
            return /* Box 2 */ ;
        }
    }
}

The appropriate expressions for the two boxes B1 and B2 are

B1: (1 + height(n->right))
B2: (1 + max(h1, h2))

B1: height(n->right)
B2: (1 + max(h1, h2))

B1: height(n->right)
B2: max(h1, h2)

B1: (1 + height(n->right))
B2: max(h1, h2)

Official answer and solution

Official answer: A
From: Official GATE 2012 answer key

Solution

Analyze binary tree height recursion base cases and recursive combiner expressions.

Definition: The height of a tree is the number of edges on the longest root-to-leaf path. A tree with only one node (root without children) has height 0.
Analysis of Box 1:

Code branch: if (n->left == NULL)
if (n->right == NULL) return 0; (leaf node has height 0)
else return /* Box 1 */ ;
When n->left == NULL but n->right != NULL, the height of the tree at $n$ is 1 edge plus the height of the right subtree: (1 + height(n->right)).

Analysis of Box 2:

Code branch: else (meaning n->left != NULL)
h1 = height(n->left);
if (n->right == NULL) return (1 + h1);
else { h2 = height(n->right); return /* Box 2 */ ; }
When both children are present, the height is 1 edge plus the maximum of the left and right subtree heights: (1 + max(h1, h2)).

Therefore:

Box 1: (1 + height(n->right))
Box 2: (1 + max(h1, h2))

This matches option (A).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 47 of 65, printed as CS Q.47
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source