A computer science problem by Thaddeus Abiy
An AVL tree is a balanced binary search tree where every node in the tree satisfies the following property:
The height difference between its left and right children is at most 1.
Let be the minimum number of nodes in an AVL tree of height . What is ?
The answer is 4024.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
It’s easy to see that N 0 = 1 N 1 = 2 N h = N h − 1 + N h − 2 + 1 With modular arithmetic’s properties we can compute the answer easily