Skip to interview prep
Apexed

186. What is the minimum number of nodes in an AVL tree of height h, and what does it imply?

HardTrees

Technical
Show model answer

The sparsest AVL tree of height h has a root, one subtree of height h - 1 and the other of height h - 2, each themselves minimal. So N(h) = N(h - 1) + N(h - 2) + 1 with N(0) = 1 and N(1) = 2 (height in edges): 1, 2, 4, 7, 12, 20, ... This is N(h) = F(h + 3) - 1, where F is the Fibonacci sequence with F(1) = F(2) = 1.

Because Fibonacci numbers grow like powers of the golden ratio, n >= N(h) implies h <= about 1.44 log2(n + 2), so AVL operations are O(log n). The maximum node count for height h is 2^(h+1) - 1, as for any binary tree.

What is the minimum number of nodes in an AVL tree of height h, and what does it imply — Data structures & algorithms interview question — Apexed