Colour a binary tree to be a red-black tree

Question

A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition).

I was wondering if we can do something similar with Red-Black trees.

Given an arbitrary uncoloured binary tree (with NULL nodes), is there a "fast" algorithm which can determine if we can colour (and find a colouring) the nodes Red/Black so that they satisfy all the properties of a Red-Black tree (definition as in this question)?

An initial thought was that we can just remove the NULL nodes and try to recursively verify if the resulting tree can be a red-black tree, but that didn't seem to go anywhere.

I did (a brief) web search for papers, but could not seem to find any which seem to deal with this problem.

It is possible that I am missing something simple.

• Karolis Juodelė: I'm pretty sure a tree can be red-black colored iff for each node, the longest path from it to a NULL node is no more than twice longer than the shortest one. Is that fast enough?

Answer 1

If for each node of a tree, the longest path from it to a leaf node is no more than twice longer than the shortest one, the tree has a red-black coloring.

Here's an algorithm to figure out the color of any node n

if n is root,
 n.color = black
 n.black-quota = height n / 2, rounded up.
else if n.parent is red,
 n.color = black
 n.black-quota = n.parent.black-quota.
else (n.parent is black)
 if n.min-height < n.parent.black-quota, then
 error "shortest path was too short"
 else if n.min-height = n.parent.black-quota then
 n.color = black
 else (n.min-height > n.parent.black-quota)
 n.color = red
 either way,
 n.black-quota = n.parent.black-quota - 1

Here n.black-quota is the number of black nodes you expect to see going to a leaf, from node n and n.min-height is the distance to the nearest leaf.

For brevity of notation, let $b(n) = $ n.black-quota, $h(n) = $ n.height and $m(n) = $ n.min-height.

Theorem: Fix a binary tree $T$. If for every node $n \in T,ドル $h(n) \leq 2m(n)$ and for node $r = \text{root}(T),ドル $b(r) \in [\frac{1}{2}h(r), m(r)]$ then $T$ has a red-black coloring with exactly $b(r)$ black nodes on every path from root to leaf.

Proof: Induction over $b(n)$.

Verify that all four trees of height one or two satisfy the theorem with $b(n) = 1$.

By definition of red-black tree, root is black. Let $n$ be a node with a black parent $p$ such that $b(p) \in [\frac{1}{2}h(p), m(p)]$. Then $b(n) = b(p) -1,ドル $h(n) = h(p)-1$ and $h(n) \geq m(n) \geq m(p)-1$.

Assume the theorem holds for all trees with root $r,ドル $b(r) < b(q)$.

If $b(n) = m(n),ドル then $n$ can be red-black colored by the inductive assumption.

If $b(p) = \frac{1}{2}h(p)$ then $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$. $n$ does not satisfy the inductive assumption and thus must be red. Let $c$ be a child of $n$. $h(c) = h(p)-2$ and $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$. Then $c$ can be red-black colored by the inductive assumption.

Note that, by the same reasoning, if $b(n) \in (\frac{1}{2}h(r), m(r)),ドル then both $n$ and a child of $n$ satisfy the inductive assumption. Therefore $n$ could have any color.

• Karolis Juodelė: @Aryabhata, any traversal is fine, as long as the parent is seen before its children. I don't have a formal proof written, but I have an idea of how it would look. I'll try writing something up when I can.
• Karolis Juodelė: @Aryabhata, i added a proof. Sorry I took so long.
• Karolis Juodelė: @Aryabhata, the idea is that if $b(p)$ of some node $p$ is withing certain bounds, a child or grandchild $c$ of $p$ can have $b(c)$ within those same bounds. Having $b(n)$ in those bounds may correspond to $n$ being black. Most of the proof is about bounding $h$ and $m$ of a child or grandchild, given $h$ and $m$ of the parent or grandparent. Your tree is certainly colorable. $b(root) = 8,ドル left child is black and right child is red, the path of length 16 is $brbrbr\dots,ドル the path of length 8 is $bbbbbbbb,ドル paths of 9 and 12 can have multiple valid colorings.
• David Richerby: There's a question about this answer.

Answer 2

I believe Karolis' answer is correct (and a pretty nice characterization of red-black trees, giving an $O(n)$ time algorithm), just wanted to add another possible answer.

One approach is to use dynamic programming.

Given a tree, for each node $n,ドル you construct two sets: $S_R(n)$ and $S_B(n)$ which contains the possible black-heights for the subtree rooted at $n$. $S_R(n)$ contains the black-heights assuming $n$ is coloured Red, and $S_B(n)$ assuming $n$ is coloured black.

Now given the sets for $n.Left$ and $n.Right$ (i.e direct children of $n$), we can compute the corresponding sets for $n,ドル by taking appropriate intersections and unions (and incrementing as needed).

I believe this comes out be an $O(n \log n)$ time algorithm.