# Prove that every thin AVL tree may be converted to red-black tree

Let's define thin AVL tree as AVL tree $t'$ such that contains minimal possible number of nodes among all AVL tree $t$ such that $height(t)=height(t')$.

I am trying to prove that every thin AVL tree may be colored to be red-black tree. I would like to use induction. I tried to do induction by height - but as you could see Every AVL tree may be red black tree I didn't managed to (I have very similar problem).

Could you give me a hint ?

I can see following thing:
thin avl tree of height $h$ has exactly one vertex on height $h$ - contrary avl tree wouldn't be thin. Moreover this node must be red (property of black height).
Example:

• I suggest you spend more time on it. Draw some thin AVL trees and see how to color them. Try to spot a pattern. Then try a proof by induction; you might have to strengthen the induction hypothesis. Jan 3 '16 at 0:22
• strenghen ? hmm, it is not truth for arbitrary tree Jan 3 '16 at 13:22
• Well, that's not the correct way to strengthen the induction hypothesis, then. Jan 3 '16 at 13:35

Your "thin" trees are sometimes know as Fibonacci trees. A Fibonacci tree $T_h$ of height $h$ is recursively defined as root with two subtrees $T_{h-1}$ and $T_{h-2}$. Hence the name.
As the number of black nodes along each path from root to leaf must be equal, this means that the subtrees $T_{h-1}$ and $T_{h-2}$ must have the same black height in $T_h$, although they differ in height.