# Forming red-black tree from binary tree conserving in-order traversal

What is the optimal algorithm (in terms of time complexity) that can transform any binary tree to a red-black tree, with the requirement that in-order traversal must yield the same values for the new tree?

Is iterative insertion of the original nodes sufficient, or can it be done with better complexity?

• (Why do I smell assignment?) Time complexity for problem size to infinity, disregarding constant factors? From tag binary-search-trees not being used for this post, I conclude the "input binary tree" not to be ordered (with regard to the order for the "output red-black tree"). There is a lower bound for comparison-based sorting, and an upper bound for RB-tree insertion. (That said, I tend to constructing balanced trees when/once the number&order of keys is known. If the input is easily iterated in order, consider how to avoid the worst case using just iterative insertion.) May 14, 2017 at 15:21

Iterative insertion gives a time complexity of $O(n \log n)$ for $n$ keys, but it's possible to do it in linear time.

The input tree gives you the in-order traversal, so you can begin by traversing the input tree and storing the keys in an array. Now, notice that if $n = 2^m - 1$ for some $m$, it's actually trivial to create a new binary tree which is perfectly balanced: split the array in half, choose the middle element as the root, and recursively build the left and right children from the two halves of the array. To make it a red-black tree, you have to assign colors. For a perfectly balanced tree, this is simple: you can actually make every node black.

But how do you handle the general case, when $n$ is not one less than a power of 2? You won't be able to make a perfectly balanced tree, but you can get pretty darn close!

This smells like a homework assignment, so I'll leave the specifics of assigning colors to you, but here's something to get started. Notice that, when you split the array of keys in half, the two halves have either exactly the same number of keys, or they differ by one. When they have exactly the same number of keys, assigning colors is easy. When they don't, you might need to use some red nodes...