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?