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

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!