Question 1

link

Convert a BST to max heap.

Solution

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

link

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

possible?

Solution

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).