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.

### 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);

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