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.
Examples:
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.
C++
// C++ implementation to convert the given // BST to Min Heap #include <bits/stdc++.h> using namespace std; // structure of a node of BST struct Node { int data; Node *left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */struct Node* getNode(int data) { struct Node *newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // function prototype for preorder traversal // of the given tree void preorderTraversal(Node*); // function for the inorder traversal of the tree // so as to store the node values in 'arr' in // sorted order void inorderTraversal(Node *root, vector<int>& arr) { if (root == NULL) return; // first recur on left subtree inorderTraversal(root->left, arr); // then copy the data of the node arr.push_back(root->data); // now recur for right subtree inorderTraversal(root->right, arr); } // function to convert the given BST to MIN HEAP // performs preorder traversal of the tree void BSTToMinHeap(Node *root, vector<int> arr, int *i) { if (root == NULL) return; // first copy data at index 'i' of 'arr' to // the node root->data = arr[++*i]; // then recur on left subtree BSTToMinHeap(root->left, arr, i); // now recur on right subtree BSTToMinHeap(root->right, arr, i); } // utility function to convert the given BST to // MIN HEAP void convertToMinHeapUtil(Node *root) { // vector to store the data of all the // nodes of the BST vector<int> arr; int i = -1; // inorder traversal to populate 'arr' inorderTraversal(root, arr); // BST to MIN HEAP conversion BSTToMinHeap(root, arr, &i); } // function for the preorder traversal of the tree void preorderTraversal(Node *root) { if (!root) return; // first print the root's data cout << root->data << " "; // then recur on left subtree preorderTraversal(root->left); // now recur on right subtree preorderTraversal(root->right); } // Driver program to test above int main() { // BST formation struct Node *root = getNode(4); root->left = getNode(2); root->right = getNode(6); root->left->left = getNode(1); root->left->right = getNode(3); root->right->left = getNode(5); root->right->right = getNode(7); convertToMinHeapUtil(root); cout << "Preorder Traversal:" << endl; preorderTraversal(root); return 0; } |
Python3
# C++ implementation to convert the # given BST to Min Heap # structure of a node of BST class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # function for the inorder traversal # of the tree so as to store the node # values in 'arr' in sorted order def inorderTraversal(root, arr): if root == None: return # first recur on left subtree inorderTraversal(root.left, arr) # then copy the data of the node arr.append(root.data) # now recur for right subtree inorderTraversal(root.right, arr) # function to convert the given # BST to MIN HEAP performs preorder # traversal of the tree def BSTToMinHeap(root, arr, i): if root == None: return # first copy data at index 'i' of # 'arr' to the node i[0] += 1 root.data = arr[i[0]] # then recur on left subtree BSTToMinHeap(root.left, arr, i) # now recur on right subtree BSTToMinHeap(root.right, arr, i) # utility function to convert the # given BST to MIN HEAP def convertToMinHeapUtil(root): # vector to store the data of # all the nodes of the BST arr = [] i = [-1] # inorder traversal to populate 'arr' inorderTraversal(root, arr); # BST to MIN HEAP conversion BSTToMinHeap(root, arr, i) # function for the preorder traversal # of the tree def preorderTraversal(root): if root == None: return # first print the root's data print(root.data, end = " ") # then recur on left subtree preorderTraversal(root.left) # now recur on right subtree preorderTraversal(root.right) # Driver Code if __name__ == '__main__': # BST formation root = Node(4) root.left = Node(2) root.right = Node(6) root.left.left = Node(1) root.left.right = Node(3) root.right.left = Node(5) root.right.right = Node(7) convertToMinHeapUtil(root) print("Preorder Traversal:") preorderTraversal(root) # This code is contributed # by PranchalK |
Output:
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.
leave a comment
0 Comments