Is it possible to construct a binary search tree from a Max-Heap in O(n) steps?

Question

I think it is not possible because if it actually is, people would build max-heap and then use it to construct BST which I think is not the case.

Please give an answer with a proof.

Answer 1

No you cannot.

The bottom level of the heap, which can contain over half the nodes, may be completely unordered in the heap. (imagine that all the internal nodes are less than all the leaf nodes).

Building a BST would determine the order of these nodes, but sorting takes O(n log n) time, so you cannot build a BST in O(n) time.