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$. 953
$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. 610