I'm currently trying to figure out this exercise (sorry for link to image, it's for the red-black trees):
http://i.imgur.com/IKMCkVf.png
And I do know that the correct one is number three from the left. However, I can't figure out why it is the correct one.
I know that the first one from the left is wrong, because it contains a red node with a red child which is not allowed. Regarding number two from the left, I guess it is wrong because of it's balance (height?).
I have read something about that a red-black tree must have a height equal to log2(n) where n is the number of nodes, but when I calculate this I still can't figure out why number three is the correct answer.
Can someone help me? Thank you!