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.

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.

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.