The problem is to implement a convert method to convert a given Max Heap into a Binary Search Tree (BST) with the condition that the output BST needs to be also a Complete Binary Tree.
Note that we assume:
- The number of elements in the Max Heap tree is always 2^L - 1 , which L is the number of levels in the tree.
- There is no duplicate element in the Max Heap.
- The Max Heap class has add and remove methods to construct and access the elements in the Heap.
- The MyBST class has insert method.
- The Solution class contains the header of the convert method. It needs a MaxHeap and a MyBST to convert the Max Heap to a Complete BST.
- The Driver class, will construct the MaxHeap and an empty BST and pass it to the convert method.
Example:
Input to convert method (a Max Heap):
7
/ \
6 5
/ \ / \
3 4 1 2
Convert Method Output (BST):
4
/ \
2 6
/ \ / \
1 3 5 7
class Solution{
public static void convert(MaxHeap maxHeap, MyBST bst){
// Write your code here, you can add more methods
}
}
