# 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!