Is the tree shown a valid red-black tree?

I have made a red-black tree and I think that it is not valid. Could someone please verify?

            B
/    \
/      \
/        \
/          \
R           R
/  \       /      \
B    B     B        B
/   \     /  \
R    R   R    R
/ \  / \ / \  / \
B  B  B B B  B B  B


As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes and these NULL nodes are considered to be black.

• If we consider the order root->left->left->left as black, then number of black nodes to that NULL node are 2.
• If we consider the node root->right->right->right->right->right as black, then number of black nodes to that NULL node are 3.

So, according to the above argument, it should not be a valid red-black tree. Am I right or am I missing some important concept?

1 Answer

You are correct $$-$$ the red-black tree you have drawn is not balanced.

For a balanced red-black tree, the number of black nodes between the root (including itself) and any leaf node (including itself) must be a constant. This is called the black height and should be a constant number that is the same regardless the path along which it is computed.

However for your tree, the path 00 results in a black height of $$2$$ and the path 1000 results in a black height of $$3$$. 0 = go left, 1 = go right.