It is required that, in a black red tree, the color for the root is always black. However, wikipedia argues that this rule can be omitted as a red root can always be changed to black but not vice versa. I get the first half, that a red root can be changed to black at any time, but in what circumstance is it impossible to change a black node to red?

For instance, consider the branch: black--red--black--red--black. We can always change it to red--black--black--red--black, since a black node does not need to have red children.


1 Answer 1


The root colour of a red-black tree carries no significance. In fact, you can save memory by not encoding it. Didactically, it is meaningful to talk about a root's colour to illustrate what it means to be red or black, because it is a special case because it has no parent which is going to count it when it evaluates the sixth restriction in Wikipedia's list (that the path from a particular node to a leaf should contain the same number of black nodes).

As for your more general question about when changing a black node to a red one is allowed: a set of nodes can be repainted if afterwards, the black-height criterion is still satisfied. For example, if a row of the tree is saturated (if it is at depth $k$, there are $2^{k}$ nodes), then you can colour that row black. You may not colour only part of a (saturated or not) red row black. Another example: in the tree $1:red \rightarrow\{ 2:black, 3:black\rightarrow\{4:red, 5:red\}\}$, you can flip the colours of $\{3,4,5\}$ and still have a legal RB tree. This is true generally for subtrees of even height and alternating colours. Maybe you can think of more examples.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.