What should a 4-node red-black tree look like

Question

Hi I know little about red-black tree before and maybe it's a stupid question.
Here's a 4-node tree:

Is it a legal red-balck tree? In my opinion, it actually violates rules of red-black tree:

3. Every red node has both of its children colored black.
4. Every path from the root to a tree leaf contains the same number (the "black-height") of black nodes.

If not what should a 4-node red-black look like?
Thanks

Answer 1

You are correct that this tree violates the rules of red-black trees because the path 3-2-1-Null goes through 3 black nodes, while 3-4-Null only goes through 2.

Recall that there is no constraint that black nodes have to have their children painted red, only the reverse. Even a tree with all black nodes is technically a red-black tree, as long as it is balanced and therefore satisfies that "Every path from the root to a tree leaf contains the same number (the 'black-height') of black nodes."

As a result, you could make this tree a valid red-black tree by painting nodes 2 and 4 black and painting node 1 red. Notice node 1 (the only red node) would still have 2 black children and all paths from the root to leaves would hit 3 black nodes. Therefore satisfying the rules of a red-black tree.