Search code examples
algorithmtreered-black-tree

Red Black Tree question

Can a node in a red black tree have one red and one black child?

I have the following tree, I have specified just the colors here. The leaf nodes are ignored.

                   B
           R               B
       B       B       R       R 
     R   R       R
Solution

  • Yes, a node can have differently coloured children. See, for example, the diagram at the very top of the MathWorld article on R-B trees; you can verify that it satisfies all the requirements for a R-B tree, and one of its nodes has children of different colours. As, for that matter, does the example you gave.