techInterview Discussion

A part of answers to technical interview questions.

Your host: Michael Pryor

Sorting array representation of a complete binary search tree

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 ( but no correct solution was found.
dbenhur Send private email
Saturday, June 26, 2010
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)


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.)
d Send private email
Saturday, June 26, 2010
This can be solved in a similar way to shuffling problems.
I believe there should some textbook solutions... Not sure
Yaxiong Zhao
Monday, June 28, 2010
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!
dbenhur Send private email
Monday, June 28, 2010

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz