Convert BST to Max Heap
Given a Binary Search Tree which is also a Complete Binary Tree. The problem is to convert a given BST into a Special Max 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 to all the nodes in the so-converted Max Heap.
Examples:
Input: 4 / \ 2 6 / \ / \ 1 3 5 7 Output: 7 / \ 3 6 / \ / \ 1 2 4 5 The given BST has been transformed into a Max Heap. All the nodes in the Max Heap satisfy the given condition, that is, values in the left subtree of a node should be less than the values in the right a subtree of the node.
Pre Requisites: Binary Search Tree | Heaps
Approach 1 :
- 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 postorder traversal of the tree.
- While traversing the root during the postorder traversal, one by one copy the values from the array arr[] to the nodes.
Implementation:
C++
// C++ implementation to convert a given // BST to Max Heap #include <bits/stdc++.h> using namespace std; 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 postorder traversal // of the given tree void postorderTraversal(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); } void BSTToMaxHeap(Node* root, vector< int > &arr, int * i) { if (root == NULL) return ; // recur on left subtree BSTToMaxHeap(root->left, arr, i); // recur on right subtree BSTToMaxHeap(root->right, arr, i); // copy data at index 'i' of 'arr' to // the node root->data = arr[++*i]; } // Utility function to convert the given BST to // MAX HEAP void convertToMaxHeapUtil(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 MAX HEAP conversion BSTToMaxHeap(root, arr, &i); } // Function to Print Postorder Traversal of the tree void postorderTraversal(Node* root) { if (!root) return ; // recur on left subtree postorderTraversal(root->left); // then recur on right subtree postorderTraversal(root->right); // print the root's data cout << root->data << " " ; } // Driver Code 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); convertToMaxHeapUtil(root); cout << "Postorder Traversal of Tree:" << endl; postorderTraversal(root); return 0; } |
Java
// Java implementation to convert a given // BST to Max Heap import java.util.*; class GFG { static int i; static class Node { int data; Node left, right; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static Node getNode( int data) { Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null ; return newNode; } // Function for the inorder traversal of the tree // so as to store the node values in 'arr' in // sorted order static void inorderTraversal(Node root, Vector<Integer> arr) { if (root == null ) return ; // first recur on left subtree inorderTraversal(root.left, arr); // then copy the data of the node arr.add(root.data); // now recur for right subtree inorderTraversal(root.right, arr); } static void BSTToMaxHeap(Node root, Vector<Integer> arr) { if (root == null ) return ; // recur on left subtree BSTToMaxHeap(root.left, arr); // recur on right subtree BSTToMaxHeap(root.right, arr); // copy data at index 'i' of 'arr' to // the node root.data = arr.get(i++); } // Utility function to convert the given BST to // MAX HEAP static void convertToMaxHeapUtil(Node root) { // vector to store the data of all the // nodes of the BST Vector<Integer> arr = new Vector<Integer>(); int i = - 1 ; // inorder traversal to populate 'arr' inorderTraversal(root, arr); // BST to MAX HEAP conversion BSTToMaxHeap(root, arr); } // Function to Print Postorder Traversal of the tree static void postorderTraversal(Node root) { if (root == null ) return ; // recur on left subtree postorderTraversal(root.left); // then recur on right subtree postorderTraversal(root.right); // print the root's data System.out.print(root.data + " " ); } // Driver Code public static void main(String[] args) { // BST formation 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 ); convertToMaxHeapUtil(root); System.out.print( "Postorder Traversal of Tree:" + "\n" ); postorderTraversal(root); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to convert a given # BST to Max Heap i = 0 class Node: def __init__( self ): self .data = 0 self .left = None self .right = None # Helper function that allocates a new node # with the given data and None left and right # pointers. def getNode(data): newNode = Node() newNode.data = data newNode.left = newNode.right = None return newNode arr = [] # Function for the inorder traversal of the tree # so as to store the node values in 'arr' in # sorted order def inorderTraversal( root): if (root = = None ): return arr # first recur on left subtree inorderTraversal(root.left) # then copy the data of the node arr.append(root.data) # now recur for right subtree inorderTraversal(root.right) def BSTToMaxHeap(root): global i if (root = = None ): return None # recur on left subtree root.left = BSTToMaxHeap(root.left) # recur on right subtree root.right = BSTToMaxHeap(root.right) # copy data at index 'i' of 'arr' to # the node root.data = arr[i] i = i + 1 return root # Utility function to convert the given BST to # MAX HEAP def convertToMaxHeapUtil( root): global i # vector to store the data of all the # nodes of the BST i = 0 # inorder traversal to populate 'arr' inorderTraversal(root) # BST to MAX HEAP conversion root = BSTToMaxHeap(root) return root # Function to Print Postorder Traversal of the tree def postorderTraversal(root): if (root = = None ): return # recur on left subtree postorderTraversal(root.left) # then recur on right subtree postorderTraversal(root.right) # print the root's data print (root.data ,end = " " ) # Driver Code # BST formation 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 ) root = convertToMaxHeapUtil(root) print ( "Postorder Traversal of Tree:" ) postorderTraversal(root) # This code is contributed by Arnab Kundu |
C#
// C# implementation to convert a given // BST to Max Heap using System; using System.Collections.Generic; public class GFG { static int i; public class Node { public int data; public Node left, right; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static Node getNode( int data) { Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null ; return newNode; } // Function for the inorder traversal of the tree // so as to store the node values in 'arr' in // sorted order static void inorderTraversal(Node root, List< int > arr) { if (root == null ) return ; // first recur on left subtree inorderTraversal(root.left, arr); // then copy the data of the node arr.Add(root.data); // now recur for right subtree inorderTraversal(root.right, arr); } static void BSTToMaxHeap(Node root, List< int > arr) { if (root == null ) return ; // recur on left subtree BSTToMaxHeap(root.left, arr); // recur on right subtree BSTToMaxHeap(root.right, arr); // copy data at index 'i' of 'arr' to // the node root.data = arr[i++]; } // Utility function to convert the given BST to // MAX HEAP static void convertToMaxHeapUtil(Node root) { // vector to store the data of all the // nodes of the BST List< int > arr = new List< int >(); int i = -1; // inorder traversal to populate 'arr' inorderTraversal(root, arr); // BST to MAX HEAP conversion BSTToMaxHeap(root, arr); } // Function to Print Postorder Traversal of the tree static void postorderTraversal(Node root) { if (root == null ) return ; // recur on left subtree postorderTraversal(root.left); // then recur on right subtree postorderTraversal(root.right); // print the root's data Console.Write(root.data + " " ); } // Driver Code public static void Main(String[] args) { // BST formation 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); convertToMaxHeapUtil(root); Console.Write( "Postorder Traversal of Tree:" + "\n" ); postorderTraversal(root); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation to convert a given // BST to Max Heap let i = 0; class Node { constructor() { this .data = 0; this .left = this .right = null ; } } /* Helper function that allocates a new node with the given data and null left and right pointers. */ function getNode(data) { let newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null ; return newNode; } // Function for the inorder traversal of the tree // so as to store the node values in 'arr' in // sorted order function inorderTraversal(root, arr) { if (root == null ) return ; // first recur on left subtree inorderTraversal(root.left, arr); // then copy the data of the node arr.push(root.data); // now recur for right subtree inorderTraversal(root.right, arr); } function BSTToMaxHeap(root,arr) { if (root == null ) return ; // recur on left subtree BSTToMaxHeap(root.left, arr); // recur on right subtree BSTToMaxHeap(root.right, arr); // copy data at index 'i' of 'arr' to // the node root.data = arr[i++]; } // Utility function to convert the given BST to // MAX HEAP function convertToMaxHeapUtil(root) { // vector to store the data of all the // nodes of the BST let arr = []; // inorder traversal to populate 'arr' inorderTraversal(root, arr); // BST to MAX HEAP conversion BSTToMaxHeap(root, arr); } // Function to Print Postorder Traversal of the tree function postorderTraversal(root) { if (root == null ) return ; // recur on left subtree postorderTraversal(root.left); // then recur on right subtree postorderTraversal(root.right); // print the root's data document.write(root.data + " " ); } // Driver Code // BST formation let 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); convertToMaxHeapUtil(root); document.write( "Postorder Traversal of Tree:" + "\n" ); postorderTraversal(root); // This code is contributed by rag2127 </script> |
Output
Postorder Traversal of Tree: 1 2 3 4 5 6 7
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
Approach 2 : (Using Heapify Up/Max Heap)
- Create an array q[] of size n, where n is the number of nodes in the given BST.
- Traverse the BST and append each node into the array using level order traversal.
- Call heapify_up to create max-heap for each element in array q[] from 1 to n so that the array q[] will be arranged in descending order using max-heap.
- Update the root and child of each node of the tree using array q[] like creating a new tree from array q[].
Implementation:
C++
#include <bits/stdc++.h> using namespace std; // Defining the structure of the Node class class Node { public : int data; Node *left, *right; Node( int data) { this ->data = data; left = right = NULL; } }; // Function to find the parent index of a node int parent( int i) { return (i - 1) / 2; } // Function to heapify up the node to arrange in max-heap order void heapify_up(vector<Node*>& q, int i) { while (i > 0 && q[parent(i)]->data < q[i]->data) { swap(q[i], q[parent(i)]); i = parent(i); } } // Function to convert BST to max heap Node* convertToMaxHeapUtil(Node* root) { if (root == NULL) { return root; } // Creating a vector for storing the nodes of BST vector<Node*> q; q.push_back(root); int i = 0; while (q.size() != i) { if (q[i]->left != NULL) { q.push_back(q[i]->left); } if (q[i]->right != NULL) { q.push_back(q[i]->right); } i++; } // Calling heapify_up for each node in the vector for ( int i = 1; i < q.size(); i++) { heapify_up(q, i); } // Updating the root as the maximum value in heap root = q[0]; i = 0; // Updating left and right nodes of BST using vector while (i < q.size()) { if (2 * i + 1 < q.size()) { q[i]->left = q[2 * i + 1]; } else { q[i]->left = NULL; } if (2 * i + 2 < q.size()) { q[i]->right = q[2 * i + 2]; } else { q[i]->right = NULL; } i++; } return root; } // Function to print postorder traversal of the tree void postorderTraversal(Node* root) { if (root == NULL) { return ; } // Recurring on left subtree postorderTraversal(root->left); // Recurring on right subtree postorderTraversal(root->right); // Printing the root's data cout << root->data << " " ; } // Driver code int main() { // Creating the BST Node* root = new Node(4); root->left = new Node(2); root->right = new Node(6); root->left->left = new Node(1); root->left->right = new Node(3); root->right->left = new Node(5); root->right->right = new Node(7); // Converting the BST to max heap root = convertToMaxHeapUtil(root); // Printing the postorder traversal of the tree cout << "Postorder Traversal of Tree: " ; postorderTraversal(root); return 0; } |
Java
// Java code implementation: import java.io.*; import java.util.*; // Defining the structure of the Node class class Node { int data; Node left, right; Node( int data) { this .data = data; left = right = null ; } } class GFG { // Function to find the parent index of a node static int parent( int i) { return (i - 1 ) / 2 ; } // Function to heapify up the node to arrange in // max-heap order static void heapify_up(List<Node> q, int i) { while (i > 0 && q.get(parent(i)).data < q.get(i).data) { Collections.swap(q, i, parent(i)); i = parent(i); } } // Function to convert BST to max heap static Node convertToMaxHeapUtil(Node root) { if (root == null ) { return root; } // Creating a list for storing the nodes of BST List<Node> q = new ArrayList<Node>(); q.add(root); int i = 0 ; while (q.size() != i) { if (q.get(i).left != null ) { q.add(q.get(i).left); } if (q.get(i).right != null ) { q.add(q.get(i).right); } i++; } // Calling heapify_up for each node in the list for ( int j = 1 ; j < q.size(); j++) { heapify_up(q, j); } // Updating the root as the maximum value in heap root = q.get( 0 ); i = 0 ; // Updating left and right nodes of BST using list while (i < q.size()) { if ( 2 * i + 1 < q.size()) { q.get(i).left = q.get( 2 * i + 1 ); } else { q.get(i).left = null ; } if ( 2 * i + 2 < q.size()) { q.get(i).right = q.get( 2 * i + 2 ); } else { q.get(i).right = null ; } i++; } return root; } // Function to print postorder traversal of the tree static void postorderTraversal(Node root) { if (root == null ) { return ; } // Recurring on left subtree postorderTraversal(root.left); // Recurring on right subtree postorderTraversal(root.right); // Printing the root's data System.out.print(root.data + " " ); } public static void main(String[] args) { // Creating the BST Node root = new Node( 4 ); root.left = new Node( 2 ); root.right = new Node( 6 ); root.left.left = new Node( 1 ); root.left.right = new Node( 3 ); root.right.left = new Node( 5 ); root.right.right = new Node( 7 ); // Converting the BST to max heap root = convertToMaxHeapUtil(root); // Printing the postorder traversal of the tree System.out.println( "Postorder Traversal of Tree: " ); postorderTraversal(root); } } // This code is contributed by karthik. |
Python3
# User function Template for python3 class Node: def __init__( self ): self .data = 0 self .left = None self .right = None # Helper function that allocates a new node # with the given data and None left and right # pointers. def getNode(data): newNode = Node() newNode.data = data newNode.left = newNode.right = None return newNode # To find parent index def parent(i): return (i - 1 ) / / 2 # heapify_up to arrange like max-heap def heapify_up(q, i): while i > 0 and q[parent(i)].data < q[i].data: q[parent(i)], q[i] = q[i], q[parent(i)] i = parent(i) def convertToMaxHeapUtil(root): if root is None : return root # creating list for BST nodes q = [] q.append(root) i = 0 while len (q) ! = i: if q[i].left is not None : q.append(q[i].left) if q[i].right is not None : q.append(q[i].right) i + = 1 # calling max-heap for each iteration for i in range ( 1 , len (q)): heapify_up(q, i) # updating root as max value in heap root = q[ 0 ] i = 0 # updating left and right nodes of BST using list while i < len (q): if 2 * i + 1 < len (q): q[i].left = q[ 2 * i + 1 ] else : q[i].left = None if 2 * i + 2 < len (q): q[i].right = q[ 2 * i + 2 ] else : q[i].right = None i + = 1 return root # Function to Print Postorder Traversal of the tree def postorderTraversal(root): if (root = = None ): return # recur on left subtree postorderTraversal(root.left) # then recur on right subtree postorderTraversal(root.right) # print the root's data print (root.data, end = " " ) # Driver Code # BST formation 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 ) root = convertToMaxHeapUtil(root) print ( "Postorder Traversal of Tree:" ) postorderTraversal(root) # This code is contributed by Anvesh Govind Saxena |
C#
// C# code implementation for the above approach using System; using System.Collections.Generic; // Defining the structure of the Node class public class Node { public int data; public Node left, right; public Node( int data) { this .data = data; left = right = null ; } } public class GFG { // Function to find the parent index of a node static int parent( int i) { return (i - 1) / 2; } // Function to heapify up the node to arrange in // max-heap order static void heapify_up(List<Node> q, int i) { while (i > 0 && q[parent(i)].data < q[i].data) { Node temp = q[i]; q[i] = q[parent(i)]; q[parent(i)] = temp; i = parent(i); } } // Function to convert BST to max heap static Node convertToMaxHeapUtil(Node root) { if (root == null ) { return root; } // Creating a list for storing the nodes of BST List<Node> q = new List<Node>(); q.Add(root); int i = 0; while (q.Count != i) { if (q[i].left != null ) { q.Add(q[i].left); } if (q[i].right != null ) { q.Add(q[i].right); } i++; } // Calling heapify_up for each node in the list for ( int j = 1; j < q.Count; j++) { heapify_up(q, j); } // Updating the root as the maximum value in heap root = q[0]; i = 0; // Updating left and right nodes of BST using list while (i < q.Count) { if (2 * i + 1 < q.Count) { q[i].left = q[2 * i + 1]; } else { q[i].left = null ; } if (2 * i + 2 < q.Count) { q[i].right = q[2 * i + 2]; } else { q[i].right = null ; } i++; } return root; } // Function to print postorder traversal of the tree static void postorderTraversal(Node root) { if (root == null ) { return ; } // Recurring on left subtree postorderTraversal(root.left); // Recurring on right subtree postorderTraversal(root.right); // Printing the root's data Console.Write(root.data + " " ); } static public void Main() { // Code // Creating the BST Node root = new Node(4); root.left = new Node(2); root.right = new Node(6); root.left.left = new Node(1); root.left.right = new Node(3); root.right.left = new Node(5); root.right.right = new Node(7); // Converting the BST to max heap root = convertToMaxHeapUtil(root); // Printing the postorder traversal of the tree Console.WriteLine( "Postorder Traversal of Tree: " ); postorderTraversal(root); } } // This code is contributed by sankar. |
Javascript
// User function Template for javascript class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } } // Helper function that allocates a new node // with the given data and None left and right // pointers. function getNode(data) { let newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null ; return newNode; } // To find parent index function parent(i) { return Math.floor((i - 1) / 2); } // heapify_up to arrange like max-heap function heapify_up(q, i) { while (i > 0 && q[parent(i)].data < q[i].data) { [q[parent(i)], q[i]] = [q[i], q[parent(i)]]; i = parent(i); } } function convertToMaxHeapUtil(root) { if (root == null ) { return root; } // creating list for BST nodes let q = []; q.push(root); let i = 0; while (q.length != i) { if (q[i].left != null ) { q.push(q[i].left); } if (q[i].right != null ) { q.push(q[i].right); } i++; } // calling max-heap for each iteration for (let i = 1; i < q.length; i++) { heapify_up(q, i); } // updating root as max value in heap root = q[0]; i = 0; // updating left and right nodes of BST using list while (i < q.length) { if (2 * i + 1 < q.length) { q[i].left = q[2 * i + 1]; } else { q[i].left = null ; } if (2 * i + 2 < q.length) { q[i].right = q[2 * i + 2]; } else { q[i].right = null ; } i++; } return root; } // Function to Print Postorder Traversal of the tree function postorderTraversal(root) { if (root == null ) { return ; } // recur on left subtree postorderTraversal(root.left); // then recur on right subtree postorderTraversal(root.right); // print the root's data document.write(root.data + " " ); } // Driver Code // BST formation let 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); root = convertToMaxHeapUtil(root); document.write( "Postorder Traversal of Tree:" ); postorderTraversal(root); |
Output
Postorder Traversal of Tree: 1 2 3 4 5 6 7
Complexity Analysis:
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us