How few nodes can an AVL tree of height h have? Make one subtree as short as the condition allows: a thinnest tree of height h is a root over a thinnest tree of height h-1 and a thinnest tree of height h-2. With N(0) = 0 and N(1) = 1,
N(h) \;=\; 1 + N(h-1) + N(h-2)
Write min_avl_nodes(h) returning N(h).
Examples
Input: h = 3
Output: 4
Explanation: N(2) = 2 and N(1) = 1, so N(3) = 1 + 2 + 1 = 4.
Input: h = 0
Output: 0
Constraints
0 <= h <= 300; the answer grows like the Fibonacci numbers, so it gets long but Python's integers are exact.
Goals
- Build the sparsest tree that still meets the AVL condition
- Read a recurrence straight out of a structural argument
- See why an AVL tree of n keys can never be much taller than log n