# Binary tree To Red-Black tree

I have a question regarding the solution provided by Karolis Juodelė. Given in this question; Colour a binary tree to be a red-black tree

Black = black nodes, white = red nodes

So for this tree when I try to manually work out the code, it seems to fail on the node 17. E.G. I have a black quota of 3 so I color the root black. Afterwards I go to the left child (17) and that has the same min height (namely 17 - 21 - 23) -> so I color this black. After this black colour I cannot see how I will end up with a valid tree with 1 black node left.

So if you could provide how to solve it for this example that would be great!

Well, apparently my answer was wrong. The algorithm, at least. The theorem seems to be okay, if a little unreadable.

More in line with that proof, the algorithm should be

if n is root,   # as before
n.color = black
n.black-quota = n.height / 2, rounded up.
# black-quota could start at any value between n.height/2 and n.min-height

else if n.parent is red,   # as before
n.color = black
n.black-quota = n.parent.black-quota.

else (n.parent is black)
n.black-quota = n.parent.black-quota - 1

# check that the subtree isn't totally uncolorable
if n.min-height < n.black-quota then
error "shortest path was too short"

# use red only if the subtree is not colorable (as a tree), with given quota
if n.height <= n.black-quota*2  then
n.color = black

else
n.color = red


What I meant by the last condition is that 17 is red for the sole reason that you can't color it black i.e. $b(17) \notin [\frac{1}{2}h(17), m(17)]$.

Hopefully that works. Thanks for pointing out the error!

• Please edit your answer over there so it's correct, too! – Raphael Aug 7 '17 at 5:47