Woodstock Blog

a tech blog for general algorithmic interview questions

[Google] Heap and BST Conversion

Question 1


Convert a BST to max heap.


The second answer:

a simple (reversed) in-order traversal of the BST. It would produce a sorted array which is indeed a max-heap!

Question 2


Converting a heap to a BST in O(n) time?



Impossible. Because otherwise, we can do this:

  1. Take an array and build the heap in O(n) time
  2. Converting the heap to a BST in O(n) time (assuming)
  3. Walking the BST in O(n) time to get a sorted sequence.

Thus we sort array in O(n) time, it can’t happen.

Right way to do, is to repeatedly dequeueing maximum value from the BST, then generate the BST recursively (bottom-up approach).