Create Balanced BST from Sorted List of Integers
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!