Building Red-Black Tree from sorted array in linear time

No matter what kind of BST you are going to build. The algorithm will be the same. Only need to build balanced binary tree.

1. Place middle element to the current position
2. Place [begin; middle) elements to the left subtree.
3. Place (middle; end) elements to the right subtree.

This is O(N) algorithm. It can be shown, that the result tree will be balanced.

We have balanced tree, so by definition:

length(longest path) - length(shortest path) <= 1

So you need to mark all nodes as black, except the deepest nodes in the tree (mark them as red).

A complete binary tree of height H has 2^H-1 nodes.

To make a red black tree from a sorted list:

1. Remove every second item from the list until you have 2^H-1 items remaining for some H. Note that you will always have enough.
2. Build a complete tree out of the remaining items, all black.
3. Now attach all the items you removed to the tree. Each item will be a red node, attached to whichever of the black nodes around its proper position is a leaf.

The easiest way to do step (3) is just to do a pre-order traversal of the tree, attaching new red nodes to every black leaf until you run out of items.

NOTE: Sasha's algorithm also works, but this one obviously works.