Question

What is the maximum number of nodes in a binary tree of height h (where height is measured as the number of edges from the root to the deepest node)?

• A. \( 2^{h} + 1 \)
• B. \( 2^{h} - 1 \)
• C. \( 2^{h+1} - 1 \)
• D. \( 2^{h-1} - 1 \)

Hint:

Height in edges means h+1 levels. Sum 2^0 up to 2^h as a geometric series.

Answer 1

The Correct Option is C

Step 1: Height is defined here as the number of edges from the root to the deepest node. So the tree has levels numbered \( 0, 1, 2, \ldots, h \), giving \( h + 1 \) levels in total.

Step 2: A binary tree is packed most densely when every level is full. Level \( i \) can hold at most \( 2^{i} \) nodes.

Step 3: Sum the maximum nodes across all levels:
\[ 2^{0} + 2^{1} + 2^{2} + \cdots + 2^{h} \]
This is a geometric series with ratio 2.

Step 4: The sum of the series is
\[ \sum_{i=0}^{h} 2^{i} = 2^{h+1} - 1 \]

Step 5: Quick check with \( h = 2 \). Levels hold 1, 2, 4 nodes, total 7, and \( 2^{2+1} - 1 = 8 - 1 = 7 \). It matches.

Answer: option C.