An issue on red-black trees

Question

If I have a binary tree, and want to add the black/red property to all of its nodes to form a red-black tree, is there a way to do that if we knew that the binary tree is balanced?

Answer 1

Templatetypedef has already answered the main part of your question in a very nice way. I just wanted to add an answer to your secondary question.

Since red-black marking is used to prevent unbalanced trees from arising, it is certainly not possible to colour every search tree - if it were then it didn't achieve anything! A counterexample is this tree:

1
 \
  2
   \
    3

where all left children are null.

Answer 2

Probably the most stringent condition on red-black trees is the fact that any root-NULL path has to have the same number of black nodes in it. Therefore, one option would be to start off by running a DFS from the root to determine the length of the shortest root-NULL path. This path length gives an upper bound on the "black height" of the tree, which is the number of black nodes on any root-NULL path.

Once we have this value, we can try to assign black heights to the nodes in a way that will let us determine which nodes are red or black. One useful observation is the following: the black height of any of a node's subtrees has to be the same, since otherwise there are two root-NULL paths that will have different black heights. Therefore, for each node, if its current black height is h and the desired black height is H, we can either

• Color it red, in which case we recursively color the left and right subtrees such that they have black height H. We also force the roots of those subtrees below to be black.
• Color it black, in which case we recursively color the left and right subtrees such that they have black height H - 1. The nodes at the roots of those trees can be either color.

I think you can do this by using dynamic programming. Supposing that the desired target black height is H, we can make a table indexed by node/black depth/color triples (here, the black height is the black height of the subtree rooted at that node) that stores whether it's possible to color that node in the proper way. Let's call it T[v, h, c]. We can fill it in as follows:

• Treat NULL as a node that's black. T[null, 0, red] = false, and T[null, 0, black] = true.
• For each node, processed in an order such that v is only processed if its subtrees l and r are processed, do the following:
  • T[v, h, red] = T[l, h, black] and T[r, h, black]
  • T[v, h, black] = T[l, h - 1, c] and T[r, h - 1, c] for any color c

Once you evaluate this, you can then check if T[root, h, c] is true for any height h or color c. This should take only polynomial time.

Hope this helps!