# Maximal difference of height between two leaves in an AVL tree

What is the maximal difference between heights of leaves in an AVL tree? I am interested only in the asymptotic difference.

I am not sure about my answer - I think that it is $O(\log n)$, given the fact that at every level we may have difference equal one.

Am I right?

• We expect you to make a significant effort to try to solve it on your own before asking here, and to show us what you tried. What have you tried? Have you tried proving that it is $O(\log n)$, and what proof approaches did you try and where did you get stuck? You've been given similar advice before: draw some small examples, try to spot a pattern, and then try a proof by induction. We want to help you understand, not do your exercise for you.
– D.W.
Jan 20, 2016 at 17:20
• Jan 27, 2016 at 21:13

We consider Fibonacci tree ([TAOCP3, Knuth98, Sect. 6.2.1]) and compute the maximal height difference in it.

A Fibonacci tree of order $k$ which is constructed recursively (see an Fibonacci tree of order 6 in the figure below; also from TAOCP):

• If $k = 0$ or $k = 1$, the tree is simply a single node.
• If $k \ge 2$, the tree has a left subtree of order $k-1$ and a right subtree of order $k-2$. It is easy to verify that a Fibonacci tree is also an AVL tree.

From the figure above, we observe that the two leaves at the leftmost $l$ and at the rightmost $r$ differ most by heights ($H_l, H_r$ among all pairs of leaves. We can compute the height difference as follows.

A Fibonacci tree of order $k$ has $n = F(k+2)-1 \sim \Phi^{k+2}$ nodes in total, where $\Phi$ is the golden ratio.

$$H_l - H_r = k \text{ (leftmost path; decrease by 1}) - k/2 \text{ (rightmost path; decrease by 2}) = k/2 \text{ (maybe floor or ceiling functions here; I omit the details)}.$$

Because $n = \Phi^{k+2}$, we have $k/2 = \log_{\Phi} \sqrt{n} - 1$.

Here is an almost perfect visualization of an AVL tree. As you can see, you can increase the the maximal difference between leaves only once per level.

In other words, to have your AVL balanced you've got to keep the balance factor between $-1$ and $1$. So, if you want to maximise the highest difference between two leaves, then you don't want the balance factor to be equal $0$ in any node.

Basically, the maximal difference is $O(logn)$.

Here are some more AVL trees I've drawn to test my reasoning. I guess that the maximal level is $\lfloor log(n) \rfloor - 1$ however I am not sure.

Resources: