Maximum depth of an AVL tree

Computer Science Level 2

Consider an AVL tree with $n$ vertices. What is its maximum possible depth?

In the answer choices, $\phi = \frac{1+\sqrt{5}}{2}$ and $\phi' = \frac{1-\sqrt{5}}{2}$ .

\log_2 (n)

O(\log_{\phi'} n)

\sqrt{n}

n

O(\log_{\phi} n)

1 solution

Hasmik Garyaka
Feb 16, 2019

The minimum number of AVL nodes is Fib(h+2)-1