Minimum AVL Tree

Note that any subtree (a node together with all descendants of it) of an AVL tree is also an AVL tree. Consider an AVL tree of height $n$ . By definition of height, one of its subtrees must have height $n-1$ . Since it's an AVL tree, the other subtree must have height of at least $n-2$ .

Let $a_n$ be the minimum number of nodes that an AVL tree of height $n$ can have. Clearly, $a_0 = 0, a_1 = 1$ . The above observation shows that $a_n \ge 1 + a_{n-1} + a_{n-2}$ (1 node for the root, plus $a_{n-1}$ for the subtree with height $n-1$ , plus $a_{n-2}$ for the subtree with height at least $n-2$ ).

In fact, equality can be achieved by taking the smallest possibility; that is, to construct the minimum AVL tree of height $n$ , take two AVL trees of height $n-1$ and $n-2$ , and attach them as subtrees of the root. This works because the two subtrees don't interact other than the condition that their height difference is at most 1, and we have satisfied it by selecting one with height $n-1$ and one with height $n-2$ .

Thus, $a_n = 1 + a_{n-1} + a_{n-2}$ . Following the recurrence gives $a_{10} = \boxed{143}$ .

Additionally, consider $b_n = 1+a_n$ . We have $b_0 = 1, b_1 = 2$ , and $b_n = b_{n-1} + b_{n-2}$ for all $n \ge 2$ . This is the recurrence of the Fibonacci numbers, and in fact $b_n = F_{n+2}$ which can be proven easily by induction. Thus we obtain the general formula $a_n = F_{n+2} - 1$ , explaining why $a_{10} = F_{12} - 1 = 144 - 1 = 143$ .

Let $N(h)$ denote minimum number of nodes in an AVL tree of height $h$ . A node in a rooted tree is at an height $h$ if and only if one of its child is at height $h-1$ and the other is at height at most $h-1$ . Since the height difference of the child at AVL tree does not exceed $1$ , this leaves the following two possibilities :

(1) Both of its children are at height $h-1$

(2) One of its child is at height $h-1$ and the other is at height $h-2$ .

Hence we have the following dynamic programming recursion $N(h)= 1+ \min \bigg( 2N(h-1) , N(h-1)+N(h-2)\bigg)$ This can be readily solved for $h=10$ with the initial condition $N(0)=0, N(1)=1$ .