Build a balanced binary tree from list in linear time
Answer #2.

An alternative approach (arguably more elegant). This basically does the same operations as my other answer, just in a different order. It is as follows:

build-tree(list A of length n):
  if n == 1:
    return singleton tree of the 1 element in A.

  let m be the median element of A  # linear time select

  let L be all elements in A less than m
  let R be all elements in A greater than m

  construct a max-heap HL from L in linear time
  construct a min-heap HR from R in linear time

  let m be the root node of tree T
  let the structure of HL be the structure of all  left-children in T
  let the structure of HR be the structure of all right-children in T

  return T


Let's try an example on $[8,12,9,15,5,1,10,3,11,14,2,4,13,7,6]$. 


First we find the median $m = 8$.
We find $L = [5,1,3,2,4,7,6]$ and $R = [12,9,15,10,11,14,13]$.
Then we have max heap HL as shown below:





Then we have min heap HR as shown below:





Then we fill in the structure of T as follows:




The dotted lines represent the underlying structure of each original heap.



Analysis

The running time is as follows:


$O(n)$ for finding the median.
$O(n)$ for constructing the two heaps.
$O(n)$ for merging the two heaps.


Thus, the total time is still $O(n)$.