Red Black Tree inserting: why make nodes red when inserted?

Question

In Red Black Tree Properties doesn't contain any rule for insert node color, how ever always we are inserting red color nodes.

If we insert black color node does it violate any Properties( any rule out of 4)?

Answer 1

Yep! Suppose you have a single node in your tree:

    5 (black)

Now insert a new black node into the tree:

    5 (black)
     \
      9 (black)

Now the invariant that every root-null path in the tree has the same number of black nodes is broken, since the path from the root left has one black node and the paths from the root right each have two.

Hope this helps!