# Every AVL tree may be red black tree

I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof.

Induction for height.
Let's assume that it is truth for each AVL tree of height at most $h$.
Let's consider AVL tree $T$ of height $h+1$. Now, let's consider two subtree of $T$ - $L$ and $R$. We know that $height(R)\le h$ and $height(L)\le h$. Hence using induction hypothesis we conclude that $L$ and $R$ may be colored such that $L$ and $R$ will be red black tree. Then we may paint root - of course black color. Now $T$ is AVL and black tree.

• Do you have a specific question? We don't like "look at my proof!" questions.
– Raphael
Jan 2, 2016 at 10:17

Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule:

Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

Not every AVL tree satisfies this condition, for example the Wikipedia example doesn't.

• Look, at wikipedia example once again. What about following coluouring i.imgur.com/7gWbjl1.png ? Jan 2, 2016 at 11:55
• @user40545 That's not the coloring that your proof produces. Jan 2, 2016 at 11:57
• Ah, ok I thought that You claied that there is no possiblity to color this graph. Jan 2, 2016 at 16:30