Let \(H, I, L\), and \(N\) represent height, number of internal nodes, number of leaf nodes, and the total number of nodes respectively in a rooted binary tree.
Which of the following statements is/are always TRUE?
Answer
(A), (B), (C)
Explanation
Height here is the number of edges on the longest root-to-leaf path, so a single node has height 0; the bounds in the options use this convention.
- A holds: if \(n_{2}\) nodes have two children, the tree has exactly \(L = n_{2} + 1\) leaves, and those \(n_{2}\) nodes are internal, so \(L \le I + 1\).
- B holds: the longest path alone has \(H + 1\) nodes, and levels 0 to \(H\) hold at most \(1 + 2 + \dots + 2^{H} = 2^{H+1} - 1\) nodes.
- C holds: the first \(H\) nodes on the longest path are internal, and internal nodes can sit only on levels 0 to \(H - 1\), which hold at most \(2^{H} - 1\) nodes.
- D fails: a path of height 2 has a single leaf, so \(H \le L\) breaks, and a perfect tree has \(2^{H}\) leaves, more than \(2^{H-1}\).
Answer: A, B, C