The height of a tree is defined as the number of edges on the longest path in…
2012
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\).
The appropriate expressions for the two boxes B1 and B2 are
- A.
B1: (1+height(n
\(\to\)right))B2: (1+max(h1, h2))
- B.
B1: (height(n
\(\to\)right))B2: (1+max(h1,h2))
- C.
B1: height(n
\(\to\)right)B2: max(h1, h2)
- D.
B1: (1+ height(n
\(\to\)right))B2: max(h1, h2)
Attempted by 152 students.
Show answer & explanation
Correct answer: A
Answer: B1 = 1 + height(n->right); B2 = 1 + max(h1, h2).
Explanation:
Base cases:
If the node pointer is NULL, return -1. This convention makes a leaf node have height 0.
If both left and right are NULL, return 0 (leaf height).
Case when left child is NULL but right child exists:
There is one edge from the current node to the right child, so the node's height is 1 plus the height of the right subtree: 1 + height(n->right).
Case when left child exists (h1 = height(n->left)) and right child is NULL:
The code returns 1 + h1, which correctly counts the edge to the left child.
Case when both children exist (h2 = height(n->right)):
The node's height is one plus the larger of the two subtree heights: 1 + max(h1, h2).
Mapping to the boxed expressions in the code:
Box 1 should be: 1 + height(n->right)
Box 2 should be: 1 + max(h1, h2)
A video solution is available for this question — log in and enroll to watch it.