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.