15
10
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] ) => [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.,[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 0
s 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]
All questions on this site, whether a programming puzzle or a code golf, should have an objective primary winning criterion, so that it is possible to indisputably decide which entry should win. – Howard – 2014-01-16T06:12:21.407
@Howard Thanks. Updated with definitive criteria for winner. – Jake Wharton – 2014-01-16T06:16:00.687
1It would be very useful to have some test cases which cover the difficult cases, rather than (as at present) just the easiest one. – Peter Taylor – 2014-01-16T10:23:46.190
Is there some reason for ruling out recursion? Not that I'm looking at a recursive solution, but that seems both artificial and unnecessary. – dmckee --- ex-moderator kitten – 2014-01-16T16:37:44.847
@dmckee I had hoped it would steer people towards figuring out a function which maps indices from the input array to the output array directly. Maybe I should post my solution... – Jake Wharton – 2014-01-16T16:41:27.477
Funny. I've actually been seriously researching this problem to improve cache behavior of binary searches in a very large amount of data (how to map the index of an array so that a binary search "middle" ends up in the first element, then second or third, etc.). The idea was that since the first few compares would end up in the beginning of the arrays it would avoid at least a few cache misses (and TLB misses later). Reversing the order of the bits in the index actually kind of worked, but I dropped it after figuring out regularity of the data and implementing interpolation search instead. – Art – 2014-01-17T12:58:07.233
1Can someone explain how the list represents a BST? – justinpc – 2014-09-02T12:47:53.050