Is the tree shown a valid red-black tree?

Question

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?

Answer 1

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.