Given a binary search tree which is also a complete binary tree. The problem is to convert the given BST into a Min Heap with the condition that all the values in the left subtree of a node should be less than all the values in the right subtree of the node. This condition is applied on all the nodes in the so converted Min Heap.
Input : 4 / 2 6 / / 1 3 5 7 Output : 1 / 2 5 / / 3 4 6 7 The given BST has been transformed into a Min Heap. All the nodes in the Min Heap satisfies the given condition, that is, values in the left subtree of a node should be less than the values in the right subtree of the node.
- Create an array arr of size n, where n is the number of nodes in the given BST.
- Perform the inorder traversal of the BST and copy the node values in the arr in sorted order.
- Now perform the preorder traversal of the tree.
- While traversing the root during the preorder traversal, one by one copy the values from the array arr to the nodes.
Preorder Traversal: 1 2 3 4 5 6 7
Time Complexity: O(n)
Auxiliary Space: O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.