Red–black Tree

Valid Red–black Trees are binary search trees with following properties:

• Each node is either red or black.
• The root node is black.
• No red nodes have red children.
• All paths from the root to a null child have the same number of black nodes (black height of the tree).
• Null children are black.