Number of AVL trees [Solution]

The problem was to compute the number of AVL tree of $n$ nodes.

Solution

---

The solution is very similar to that of the corresponding problem for red-black trees.

Using dynamic programming, try to compute $T[n, h]$ the number of AVL trees on $n$ nodes with height $h$.

Now write a recursive formula based on the AVL tree properties, and you have an algorithm.

I will leave the details to you.