# Root Color of a Black Red Tree

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.

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.