Given a unique, sorted list of integers, create a balanced binary-search tree represented as an array without using recursion.
func( [1,2,3,5,8,13,21] ) => [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] ) => [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.,
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.
The outputs for simple arrays containing
n for various
n. As described above, the trailing
0s are optional.
  [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]