## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
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
Yaxiong Zhao Monday, June 28, 2010 |

Powered by FogBugz