Sparsest AVL tree — Aptitude Question
Sparsest AVL tree: What is the minimum number of nodes in an AVL tree of height 4, counting the height of a single… Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Hard
- Time target: 150 seconds
Question
What is the minimum number of nodes in an AVL tree of height 4, counting the height of a single node as 0?
Options
- 7
- 11
- 12
- 15
Show the answer and the worked solution
Correct answer: C. 12
Worked solution
- A sparsest AVL tree of height h has a root, a sparsest subtree of height h − 1 and a sparsest subtree of height h − 2, so N(h) = N(h − 1) + N(h − 2) + 1.
- N(0) = 1 and N(1) = 2.
- N(2) = 2 + 1 + 1 = 4.
- N(3) = 4 + 2 + 1 = 7.
- N(4) = 7 + 4 + 1 = 12.
Answer: 12.
The idea
The minimum-node AVL trees are the Fibonacci trees, and the recurrence N(h) = N(h−1) + N(h−2) + 1 is what proves an AVL tree's height stays O(log n).
Shortcut. The minimum is N(h) = F(h + 3) − 1 with Fibonacci 1, 1, 2, 3, 5, 8, 13, so N(4) = F(7) − 1 = 13 − 1 = 12.
Common trap. 7 is N(3), the answer one level down, which is what counting height in nodes rather than edges produces.
All Data Structures & Algorithms questions · placement mock tests