The height of a binary tree is the maximum number of edges in any root to leaf…
2007
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
- A.
2h−1
- B.
2h−1 -1
- C.
2h+1-1
- D.
2h+1
Attempted by 777 students.
Show answer & explanation
Correct answer: C
Answer: 2^(h+1) - 1
Reasoning: A binary tree of height h has levels numbered from 0 to h. Each level i has 2^i nodes.
Level 0: 2^0 = 1 node
Level 1: 2^1 nodes, level 2: 2^2 nodes, …, level h: 2^h nodes
Total nodes = sum_{i=0}^{h} 2^i
Sum of the geometric series = 2^(h+1) - 1
Therefore the maximum number of nodes in a binary tree of height h is 2^(h+1) - 1.
A video solution is available for this question — log in and enroll to watch it.