# Height of AVL tree with balance condition of 2

The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed imbalance condition between two child nodes would be 2), how could I find the maximum height of such a tree. Would I need to solve some kind of recurrence relation or fibonacci sequence. Is there an easier way of figuring out the maximum height of a tree with a balance condition of 2 by using what we already know? Thanks.

Let $$T_h$$ denote the minimal number of nodes that a standard AVL tree of height $$h$$ could have.

If $$h>0$$, then there's the root and two subtrees. One of the subtrees must have height $$h-1$$. The other must have height at least $$h-2$$, otherwise it's not a valid AVL tree. So we have the recurrence:

$$T_h = T_{h-1} + T_{h-2} + 1$$

And we can throw in $$T_0 = 0$$ and $$T_1 = 1$$ for obvious reasons.

The easy way to solve the recurrence is to denote $$F_h = T_h + 1$$. Then:

\begin{align*}F_0 & = 1 \\ F_1 & = 2 \\ F_h & = F_{h-1} + F_{h-2}\end{align*}

That is, they're Fibonacci numbers with the sequence offset by 3.

Since:

$$F_h \approx \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{h+3}$$

Inverting this, we get:

$$h \approx \frac{1}{\log \left( \frac{1 + \sqrt{5}}{2} \right)} \log \left( T_h \right) + 3$$

And that is where the 1.44 comes from.

So what you need is to solve the recurrence:

$$U_h = U_{h-1} + U_{h-3} + 1$$

with suitable initial conditions.

If you can't think of a clever way to do this, you can do it the not-clever-but-always-works way by observing that:

$$\begin{bmatrix} U_h \\ U_{h-1} \\ U_{h-2} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \begin{bmatrix} U_{h-1} \\ U_{h-2} \\ U_{h-3} \\ 1\end{bmatrix}$$

Therefore:

$$\begin{bmatrix} U_{h+2} \\ U_{h+1} \\ U_{h} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}^{h} \begin{bmatrix} U_{2} \\ U_{1} \\ U_{0} \\ 1\end{bmatrix}$$

Next, perform eigendecomposition on the matrix. Let:

$$M = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}$$

Suppose you can find a matrix $$Q$$ and a diagonal matrix $$\Lambda$$ such that $$M = Q \Lambda Q^{-1}$$. Then:

$$M^h = Q \Lambda^h Q^{-1}$$

Taking the power of a diagonal matrix is trivial, and this should give you a closed form. You will then need to find an approximate inverse to solve your problem.