Create Balanced BST from Sorted List of Integers Given a unique, sorted list of integers, create a balanced binary-search tree represented as an array without using recursion.

For example:

func( [1,2,3,5,8,13,21] ) =&gt; [5,2,13,1,3,8,21]


Before we start, a hint: we can simplify this problem a ton so that we don't actually have to think about the input integers (or any comparable object for that matter!).

If we know the input list is sorted already, it's contents are irrelevant. We can simply think about it in terms of indices into the original array.

An internal representation of the input array then becomes:

func( [0,1,2,3,4,5,6] ) =&gt; [3,1,5,0,2,4,6]


This means rather than writing something that has to deal with comparable objects, we really only need to write a function which maps from the range [0,n) to the resulting array. Once we have the new order, we can simply apply the mapping back to the values in the input to create the return array.

Valid solutions must:


Accept a zero-element array and return an empty array.
Accept an integer array of length n and return an integer array

Of length between n and the next highest power of 2 minus 1. (e.g., for input size 13 return anywhere between 13 and 15).
Array which represents a BST where the root node is at position 0 and the height is equal to log(n) where 0 represents a missing node (or a null-like value if your language allows). Empty nodes, if present, must only exist at the end of the tree (e.g., [2,1,0])



The input integer array has the following guarantees:


Values are 32-bit signed integers greater than zero.
Values are unique.
Values are in ascending order from position zero.
Values may be sparse (i.e., not adjacent to each other).


The most terse code by ascii character count wins, but I'm also interested in seeing elegant solutions for any particular language.

Test cases

The outputs for simple arrays containing 1 to n for various n. As described above, the trailing 0s are optional.

[]
[1]
[2,1,0]
[2,1,3]
[3,2,4,1,0,0,0]
[4,2,5,1,3,0,0]
[4,2,6,1,3,5,0]
[4,2,6,1,3,5,7]
[5,3,7,2,4,6,8,1,0,0,0,0,0,0,0]
[6,4,8,2,5,7,9,1,3,0,0,0,0,0,0]
[7,4,9,2,6,8,10,1,3,5,0,0,0,0,0]
[8,4,10,2,6,9,11,1,3,5,7,0,0,0,0]
[8,4,11,2,6,10,12,1,3,5,7,9,0,0,0]
[8,4,12,2,6,10,13,1,3,5,7,9,11,0,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]
Ruby, 143

s=ARGV.size;r,q=[],[[0,s]];s.times{b,e=q.shift;k=Math::log2(e-b).to_i-1;m=(e-b+2)&gt;(3&lt;&lt;k)?b+(2&lt;&lt;k)-1:e-(1&lt;&lt;k);r&lt;&lt;ARGV[m];q&lt;&lt;[b,m]&lt;&lt;[m+1,e]};p r


It is a (loosely) compressed version of the following code which basically does a BFS on the tree.

def l(n)
    k = Math::log2(n).to_i-1
    if n+2 &gt; (3&lt;&lt;k) then
        (2&lt;&lt;k)-1
    else
        n-(1&lt;&lt;k) 
    end
end

def bfs(tab)
  result = []
  queue = [[0,tab.size]]
  until queue.empty? do
    b,e = queue.shift
    m = b+l(e-b)
    result &lt;&lt; tab[m]
    queue &lt;&lt; [b,m] if b &lt; m
    queue &lt;&lt; [m+1,e] if m+1 &lt; e
  end
  result
end

p bfs(ARGV)


Besides, because it's BFS, not DFS, a requirement of non-recursive solution is not significant, and it puts some languages at a disadvantage.

Edit: Fixed solution, thanks to @PeterTaylor for his comment!