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.

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    May 23, 2014 at 21:33
  • $\begingroup$ @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? $\endgroup$
    – john_leo
    May 24, 2014 at 9:30

1 Answer 1


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}$.

Unfortunately there apparently is no known closed form for this sequence. The OEIS has a list of the first 1000 terms and maple + mathematica code to compute further ones (via the recursion).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.