Search code examples
algorithminserttreered-black-tree

Inserting into red black tree

I am taking an algorithms course and in my course slides, there is an example of insertion into a red-black tree:

enter image description here

My question is, why don't we let "2" be a leaf node here? It looks like if we let it be a leaf node, then no condition of a red black tree is violated. What am I missing here?

Solution

  • All the leaves of a Red Black tree have to be NIL Check property 3