techInterview Discussion

Complete binary search tree is represented through array. It must be sorted in O(n) and O(1) space complexity.

This problem was discussed previously (http://discuss.techinterview.org/default.asp?interview.11.468485.13) but no correct solution was found.

No one ever specified the array representation, but let's assume it's in level order, the way binary heaps are laid out.

The problem reduces to transforming

a(1) a(2) ... a(n) b(1) b(2) ... b(2*n)

into

b(1) a(1) b(2) b(3) a(2) b(4) ... b(2*n-1) a(n) b(2*n)

in place in O(n) time and O(1) space (assuming n is a power of 2, we perform merges on sub-arrays of sizes 1 + 2 + 4 + ... + n = 2*n-1). We can now use the complicated merge from in-place merge-sort. (Is there a more elegant way? Probably.)

This can be solved in a similar way to shuffling problems.
I believe there should some textbook solutions... Not sure

I thought in the same way d did - merging on level basis, but failed to find decent explanation of how in place shuffling works (in Algorithms in Java perfect shuffling is done using auxiliary array and in-place algorithm left as an exercise). May be you can point me to explained algorithm? Thanks!