Let \(T\) be a binary search tree with \(15\) nodes. The minimum and maximum…
2017
Let \(T\) be a binary search tree with \(15\) nodes. The minimum and maximum possible heights of \(T\) are:
Note: The height of a tree with a single node is \(0\).
- A.
4 and 15 respectively.
- B.
3 and 14 respectively.
- C.
4 and 14 respectively.
- D.
3 and 15 respectively.
Attempted by 367 students.
Show answer & explanation
Correct answer: B
Key idea: relate the number of nodes to tree height.
Minimum possible height: A perfect binary tree of height h has 2^(h+1) - 1 nodes. Find the smallest h with 2^(h+1) - 1 ≥ 15. Since 2^4 - 1 = 15, we get h = 3. So the minimum height is 3.
Maximum possible height: The worst-case (degenerate) BST is a chain. Its height equals number of nodes minus 1, so height = 15 - 1 = 14.
Conclusion: The minimum possible height is 3 and the maximum possible height is 14.
A video solution is available for this question — log in and enroll to watch it.