Convert BST to Min Heap

Problem Statement:

In this problem, we will be given a binary search tree and we have to convert the Binary search tree into a min-heap. This condition is applied to all the nodes in the converted Min Heap.

What is Min-Heap?

Min – Heap follows the property of a complete binary tree in which the value of the internal node is smaller than or equal to the value of the children of that node.
In 0 – based indexing, the node stored at k index in the array will have its left child held at index 2k + 1 and its right child at index 2k + 2.

What is BST?

Binary Search Tree is a type of binary tree which satisfies the following properties:

  • The left subtree of any node contains only nodes with value smaller than the parent’s node value.
  • The right subtree of any node contains only nodes with values bigger than the parent’s node value.
  • The left and right subtree each must be a BST.

Let’s take an examplefor understanding the problem statement:

In this example, all the given conditions are satisfied i.e. the value in the left subtree of a root node should be less than the values of the right subtree of the root node.

Algorithm:

  • Create an array of size n, where n is the number of nodes in the given BST.
  • Perform the inorder traversal of the BST and copy the values of the nodes in the array.
  • Now Perform the preorder traversal of the BST.
  • While traversing the BST in a preorder manner, copy the values one by one from the array to the nodes.

Dry Run:

Code Implementation

#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int data;
    Node *left, *right;
};
 
struct Node* getNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
 
void preorderTraversal(Node*);
 
void inorderTraversal(Node* root, vector<int>& arr)
{
    if (root == NULL)
        return;
 
    inorderTraversal(root->left, arr);
 
    arr.push_back(root->data);
 
    inorderTraversal(root->right, arr);
}
 
void BSTToMinHeap(Node* root, vector<int> arr, int* i)
{
    if (root == NULL)
        return;
 
    root->data = arr[++*i];
 
    BSTToMinHeap(root->left, arr, i);
 
    BSTToMinHeap(root->right, arr, i);
}
 
void convertToMinHeapUtil(Node* root)
{
    vector<int> arr;
    int i = -1;
 
    inorderTraversal(root, arr);
 
    BSTToMinHeap(root, arr, &i);
}
 
void preorderTraversal(Node* root)
{
    if (!root)
        return;
    cout << root->data << " ";
 
    preorderTraversal(root->left);
 
    preorderTraversal(root->right);
}
 
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;
}
import java.util.ArrayList;
 
class PrepBytes {
 
    static class Node {
 
        int data;
        Node left, right;
 
        Node()
        {
            this.data = 0;
            this.left = this.right = null;
        }
 
        Node(int data)
        {
            this.data = data;
            this.left = this.right = null;
        }
    }
 
    private static void preOrder(Node root)
    {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
 
    private static void bstToArray(Node root,
                                   ArrayList<Integer> arr)
    {
        if (root == null)
            return;
 
        bstToArray(root.left, arr);
 
        arr.add(root.data);
 
        bstToArray(root.right, arr);
    }
     
    static int index;
    private static void arrToMinHeap(Node root,
                                     ArrayList<Integer> arr)
    {
        if (root == null)
            return;
        root.data = arr.get(index++);
 
        arrToMinHeap(root.left, arr);
        arrToMinHeap(root.right, arr);
    }
    static void convertToMinHeap(Node root)
    {
          index = 0;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        bstToArray(root, arr);
 
        arrToMinHeap(root, arr);
    }
 
    public static void main(String[] args)
    {
 
        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);
 
        System.out.print(
            "Preorder Traversal Before Conversion :"
            + "\n");
        preOrder(root);
        convertToMinHeap(root);
 
        System.out.print(
            "\nPreorder Traversal After Conversion :"
            + "\n");
        preOrder(root);
    }
}
class Node:
 
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
 
def inorderTraversal(root, arr):
    if root == None:
        return
 
    inorderTraversal(root.left, arr)
 
    arr.append(root.data)
 
    inorderTraversal(root.right, arr)
 
 
def BSTToMinHeap(root, arr, i):
    if root == None:
        return
 
    i[0] += 1
    root.data = arr[i[0]]
 
    BSTToMinHeap(root.left, arr, i)
 
    BSTToMinHeap(root.right, arr, i)
 
 
def convertToMinHeapUtil(root):
 
    arr = []
    i = [-1]
 
    inorderTraversal(root, arr)
 
    BSTToMinHeap(root, arr, i)
 
 
def preorderTraversal(root):
    if root == None:
        return
 
    print(root.data, end=" ")
 
    preorderTraversal(root.left)
 
    preorderTraversal(root.right)
 
 
if __name__ == '__main__':
 
    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)

Time Complexity: O(N)
Space Complexity: O(N)

This article tried to discuss How to Convert BST to Min Heap. Hope this blog helps you understand the implementation. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes

Leave a Reply

Your email address will not be published. Required fields are marked *