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.


  • 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 *