Rules required for a valid Red Black Tree

• Each Node is either red or black
• The root node is black
• No red nodes have red children
• Every path from root to a nul child has the same number of black nodes (black height of tree)

An example of a valid Red Black Tree

For more information regarding red black trees refer here