Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Convert BST to Min Heap

Last Updated on December 14, 2022 by Prepbytes

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.


  • 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)
    inorderTraversal(root->left, arr);
    inorderTraversal(root->right, arr);
void BSTToMinHeap(Node* root, vector<int> arr, int* i)
    if (root == NULL)
    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)
    cout << root->data << " ";
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);
    cout << "Preorder Traversal:" << endl;
    return 0;
import java.util.ArrayList;
class PrepBytes {
    static class Node {
        int data;
        Node left, right;
   = 0;
            this.left = this.right = null;
        Node(int data)
   = data;
            this.left = this.right = null;
    private static void preOrder(Node root)
        if (root == null)
        System.out.print( + " ");
    private static void bstToArray(Node root,
                                   ArrayList<Integer> arr)
        if (root == null)
        bstToArray(root.left, arr);
        bstToArray(root.right, arr);
    static int index;
    private static void arrToMinHeap(Node root,
                                     ArrayList<Integer> arr)
        if (root == null)
            return; = 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);
            "Preorder Traversal Before Conversion :"
            + "\n");
            "\nPreorder Traversal After Conversion :"
            + "\n");
class Node:
    def __init__(self, data): = data
        self.left = None
        self.right = None
def inorderTraversal(root, arr):
    if root == None:
    inorderTraversal(root.left, arr)
    inorderTraversal(root.right, arr)
def BSTToMinHeap(root, arr, i):
    if root == None:
    i[0] += 1 = 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:
    print(, end=" ")
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)
    print("Preorder Traversal:")

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 *