# Number of Different AVL Tree

I studying the related question.

but it's not so general.

In-fact, We want to know with N keys, how many different AVL Tree, we can make?

we know with N=1 key is 1 AVL Tree. with N=2 key we have 2 different AVL Tree, but in general we can make any recurrence formula? for example for N=4, N=5 and so on.

• What have you tried on your own? Did you try working out the number for $n=1,2,3,4,5,6$ and looking for a pattern? Have you tried to derive a recurrence formula? Where did you get stuck? We want to help you, but without knowing what you tried and where you got stuck, we can't help you. Also, we expect you to make a serious effort before asking. While I'm asking: when do you count two AVL trees as "different"? And, in what context did you run into this question? – D.W. May 23 '14 at 21:33
• I'm Sorry for my lack of knowledge !! i want to know with N key, how many different AVL can be constructed? I couldn't find a pattern up to yed :(. Would U Please Help Me ! – user3661613 May 23 '14 at 21:43
• @user3661613 What do you know about easier tree enumerations? Do you know how many different binary trees with $n$ nodes there are (Hint: Catalan-Number)? Do you know how many different Binary Search trees of size $n$ there are? – john_leo May 24 '14 at 9:30

Let $a_{n,h}$ denote the number of AVL trees with $n$ nodes and height $h$. It is straightforward to get a recurrence for $a_{n,h}$:
$$a_{n,h} = \sum_{k=1}^n \bigl(a_{k-1,h-1}a_{n-k,h-1} + a_{k-1,h-1}a_{n-k,h-2} + a_{k-1,h-2}a_{n-k,h-1}\bigr),~ n\geq h > 1,$$
with the initial conditions $a_{n,h} = 0$, if $h>n$ or $h\in\{0,1\}, n\neq h$, and $a_{0,0} = a_{1,1} = 1$.
The numbers you are looking for then are $a_n = \sum_h a_{n,h}$.