The height of a tree is the length of the longest root-to-leaf path in it. The…
2015
The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are
- A.
63 and 6, respectively
- B.
64 and 5, respectively
- C.
32 and 6, respectively
- D.
31 and 5, respectively
Attempted by 462 students.
Show answer & explanation
Correct answer: A
Answer: Maximum = 63 nodes; Minimum = 6 nodes.
Reasoning (assuming height is the number of edges on the longest root-to-leaf path):
Maximum nodes: A perfect binary tree of height h has h+1 levels, and the total number of nodes is 2^{h+1} - 1. For h = 5, this gives 2^{6} - 1 = 64 - 1 = 63.
Minimum nodes: The minimum occurs in a skewed tree with exactly one node on each of the h+1 levels, so the minimum number is h+1. For h = 5, this is 5 + 1 = 6.
Note: If a different definition of height is used (for example, counting nodes instead of edges along the longest path), formulas would shift accordingly. Under the edge-count definition used here, the correct pair is 63 and 6.
A video solution is available for this question — log in and enroll to watch it.