Maximum nodes for a given height — Aptitude Question
Maximum nodes for a given height: A binary tree has height 5, taking the height of a single-node tree to be 0. Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Easy
- Time target: 60 seconds
Question
A binary tree has height 5, taking the height of a single-node tree to be 0. What is the maximum number of nodes it can contain?
Options
- 31
- 32
- 63
- 64
Show the answer and the worked solution
Correct answer: C. 63
Worked solution
- With the root on level 0, level i can hold at most 2^i nodes.
- Height 5 means levels 0 through 5 exist.
- The total is 1 + 2 + 4 + 8 + 16 + 32 = 63, which is the familiar 2^(h+1) − 1.
Answer: 63.
The idea
Fix the convention first: height counted in edges makes the maximum 2^(h+1) − 1, while height counted in nodes makes it 2^h − 1. Papers state the convention precisely because the answers differ.
Shortcut. Height 5 counted in edges means 6 full levels, 2⁶ − 1 = 63; a count of the form 2ᵏ − 1 is always odd, which rules out 32 and 64.
Common trap. 31 is 2⁵ − 1, the formula for height counted in nodes; with a single node at height 0 the tree has one more level.
All Data Structures & Algorithms questions · placement mock tests