Tutorialspoint.dev

Convert BST to Min Heap

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. 



  1. Create an array arr[] of size n, where n is the number of nodes in the given BST.
  2. Perform the inorder traversal of the BST and copy the node values in the arr[] in sorted order.
  3. Now perform the preorder traversal of the tree.
  4. 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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter