World's most popular travel blog for travel bloggers.

# [Answers] Root Color of a Black Red Tree

, ,
Problem Detail:

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.

#### Answered By : Lieuwe Vinkhuijzen

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.