Why does an AVL tree of height h has a min number of node = F(h+2) - 1

2017-01-27

An answer to this question on Stack Overflow.

Question

Question: Why does an AVL tree of height h has a min number of node = F(h+2) - 1, where F(h) is the hth Fibonacci number?

I know that a recurrence for the min number of nodes in an AVL tree with height h can be written as: N(h) = N(h-1) + N(h-2) + 1

I would like to know why N(h) = F(h+2) - 1. Do I have to solve both recurrences explicitly and plug in the numbers, or is there any other way of seeing it, since the form of N(h) = N(h-1) + N(h-2) + 1 is extremely similar to that of the Fibonacci sequence, so I assume there would be another way of doing it directly from from the Fibonacci sequence.

Answer

I provide a more extensive answer here, but this occurs because a Fibonacci tree is the sparest tree you can have before the AVL algorithm invokes a rotation and reduces the height of the tree.