CODEWITHSUNDEEP
javared-black-tree
Hello
Hello

Reputation: 286

Null child in Red-black tree Java

For the fourth rule in Red-Black rules for Red-black binary search tree(not sure if it's fourth just in my book), Every path from the root to a leaf, or to a null child, must contain the same number of black nodes, what exactly is a null child? As far as I understood, it's like a potential child that could be added to a node but in reality, it isn't there. 

......................................................
                            25(black)                                                              
            20(black)                             50(red)                              
    --              --              --                 70(black)              
......................................................

The book says this case does not follow the red-black rules and I'm not sure why. I'd assume it has something to do with a null child. Because it looks like it satisfies all the rules. The root is black, every node is either red or black, if a node is red, its child is black. And every path from the root to a leaf contains the same number of black nodes. So how exactly does the null child make this case not follow the red-black rules?

Upvotes: 1

Views: 548

Answers (1)

Alexey Romanov
Alexey Romanov

Reputation: 170815

Path 25, 50, -- has 1 black node (25); path 25, 50, 70 has 2 black nodes (25 and 70). Normally rules for red-black trees don't make a distinction between leaves and null children; we can say that the 70 node also has two null children, and it's those which are the leaves.

Upvotes: 1

Related Questions