# Convert BST to Min Heap

Difficulty Level Hard
Frequently asked in Amazon BlackRock ByteDance GE Healthcare Honeywell
Binary Search Tree Binary Tree Heap TreeViews 210

Table of Contents

## Problem Statement

Given a complete Binary Search Tree, write an algorithm to convert it into a Min Heap, which is to convert BST to Min Heap. The Min Heap should be such that the values on the left of a node must be less than the values on the right of that node.

## Example

Input

Output

Level Order : 6 7 13 9 12 18 23

## Algorithm to convert BST to Min Heap

A Binary Search Tree contains elements such that its’ in-order traversal gives the elements in sorted form. To convert BST to Min Heap we convert the in-order traversal of the Binary Search Tree in pre-order traversal, that is, we store the in-order traversal of the tree in an array and then replace the nodes in pre-order fashion with the in-order output.

This will ensure that the Binary Search Tree converts to a Min Heap and also the Min Heap satisfies the given property, that is, all the nodes in the left sub-tree of a node is smaller than all the nodes in the right sub-tree of that tree.

```1. Traverse the BST in in-order traversal and store the traversal in an array or a list.
2. This time traverse the Binary Search Tree in pre-order form.
3. Replace every node with the corresponding value stored in the array or list.```

### Time Complexity = O(N)

Since we performed in-order and pre-order traversals of the tree which take only O(N) time.

### Space Complexity = O(N)

Here we are storing n elements, thus a linear space complexity space solution/.
where N is the total number of nodes in the complete Binary Search Tree.

### Explanation

Consider the tree shown in the above example.

Step 1
Traverse the tree in in-order form and store it in an array.
arr[] = {6, 7, 9, 12, 13, 18, 23}

Step 2 & 3
Traverse the tree in pre-order form and replace every node’s value with the corresponding value stored in the array.

As we can see in the figure, the tree is converted into a Min Heap satisfying the given properties.

## Code

### Java Code to convert BST to Min Heap

```import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class ConvertBSTToMinHeap {
// class representing node of a binary tree
static class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
}
}
// function to print level order traversal of binary tree
private static void levelOrder(Node root) {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node curr = queue.poll();
System.out.print(curr.data + " ");
if (curr.left != null)
queue.add(curr.left);
if (curr.right != null)
queue.add(curr.right);
}
}
// function to store the inorder traversal of tree in a list
private static void storeInOrder(Node root, ArrayList<Integer> inOrder) {
if (root != null) {
storeInOrder(root.left, inOrder);
inOrder.add(root.data);
storeInOrder(root.right, inOrder);
}
}
// function to replace the inorder traversal with pre-order traversal
private static void replaceInOrderWithPreOrder(Node root, ArrayList<Integer> inOrder) {
if (root != null) {
root.data = inOrder.get(0);
inOrder.remove(0);
replaceInOrderWithPreOrder(root.left, inOrder);
replaceInOrderWithPreOrder(root.right, inOrder);
}
}
private static void convertToMinHeap(Node root) {
ArrayList<Integer> inOrderTraversal = new ArrayList<>();
// store the in order traversal of the tree in a list
storeInOrder(root, inOrderTraversal);
// replace the pre order traversal with in order traversal
replaceInOrderWithPreOrder(root, inOrderTraversal);
}
public static void main(String[] args) {
// Example Tree
Node root = new Node(12);
root.left = new Node(7);
root.right = new Node(18);
root.left.left = new Node(6);
root.left.right = new Node(9);
root.right.left = new Node(13);
root.right.right = new Node(23);
convertToMinHeap(root);
levelOrder(root);
System.out.println();
}
}
```
`6 7 13 9 12 18 23`

### C++ Code to convert BST to Min Heap

```#include <bits/stdc++.h>
using namespace std;

// class representing node of a binary tree
class Node {
public:
int data;
Node *left;
Node *right;

Node(int d) {
data = d;
left = right = NULL;
}
};

// function to print level order traversal of binary tree
void levelOrder(Node *root) {
if (root == NULL) {
return;
}

queue<Node*> q;
q.push(root);

while (!q.empty()) {
Node *curr = q.front();
q.pop();

cout<<curr->data<<" ";

if (curr->left != NULL)
q.push(curr->left);
if (curr->right != NULL)
q.push(curr->right);
}
}

// function to store the inorder traversal of tree in a list
void storeInOrder(Node *root, vector<int> &inOrderTraversal) {
if (root != NULL) {
storeInOrder(root->left, inOrderTraversal);
inOrderTraversal.push_back(root->data);
storeInOrder(root->right, inOrderTraversal);
}
}

// function to replace the inorder traversal with pre-order traversal
void replaceInOrderWithPreOrder(Node *root, vector<int> &inOrderTraversal) {
if (root != NULL) {
root->data = inOrderTraversal[0];
inOrderTraversal.erase(inOrderTraversal.begin());
replaceInOrderWithPreOrder(root->left, inOrderTraversal);
replaceInOrderWithPreOrder(root->right, inOrderTraversal);
}
}

void convertToMinHeap(Node *root) {
std::vector<int> inOrderTraversal;

// store the in order traversal of the tree in a list
storeInOrder(root, inOrderTraversal);

// replace the pre order traversal with in order traversal
replaceInOrderWithPreOrder(root, inOrderTraversal);
}

int main() {
// Example Tree
Node *root = new Node(12);
root->left = new Node(7);
root->right = new Node(18);
root->left->left = new Node(6);
root->left->right = new Node(9);
root->right->left = new Node(13);
root->right->right = new Node(23);

convertToMinHeap(root);
levelOrder(root);
cout<<endl;

return 0;
}```
`6 7 13 9 12 18 23`
Translate »