Home » Technical Interview Questions » Tree Interview Questions » Convert BST into a Min-Heap without using array

# Convert BST into a Min-Heap without using array

Difficulty Level Medium

## Problem Statement

“Convert BST into a Min-Heap without using array” problem states that you are given a BST (binary search tree) and you need to convert it into a min-heap. The min-heap should contain all the elements in the binary search tree. The algorithm should run in linear time complexity.

## Example

Input Output ## Approach to Convert BST into a Min-Heap without using array

### Naive Approach

“Convert BST into a Min-Heap without using array” problem can be solved if we first store the in-order traversal of the binary search tree. And after finding the in-order traversal, we start creating min-heap ( complete binary tree having all children in subtree lesser than the parent ). So, how will we create the min-heap? We will create the min-heap by level placing the elements in level order traversal that will ensure the complete binary tree property. And since we have in-order traversal we are sure that property of min-heap is satisfied (parent is smaller than both of its children). But this requires storing in-order traversal.

### Efficient Approach

We can solve this problem in O(1) space if we first convert our binary search tree into a linked list. There is a condition on the linked list as well that it must be in sorted order. For doing that, we first traverse the right subtree and then traverse the left subtree. Because we insert the nodes in the linked list at the start of it. This way, we are ensuring that the linked list remains sorted. Once, we have our sorted linked list. We rearrange the nodes’ left and right pointers such that our complete binary tree property is satisfied. As we were doing in the naive approach, we used level order traversal for creating min-heap. Here also we will use the same.

READ  Check if each internal node of a BST has exactly one child

## Code

### C++ code to Convert BST into a Min-Heap without using array

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

struct node{
int data;
node* left;
node* right;
};

node* create(int data){
node* tmp = new node();
tmp->data = data;
tmp->left = tmp->right = NULL;
return tmp;
}

// prints the level order traversal of the tree
void levelOrderTraversal(node *root)
{
if (root == NULL) return;
queue<node*> q;
q.push(root);
while(!q.empty()){
int qSize = q.size();
while(qSize--){
node* nodeAtFront = q.front();
q.pop();
if(nodeAtFront->left)
q.push(nodeAtFront->left);
if(nodeAtFront->right)
q.push(nodeAtFront->right);
cout<<nodeAtFront->data<<" ";
}
cout<<endl;
}
}

{
if(!root)
return;

//first convert right subtree into linked list
// insert root into the linked list
//if head pointer exists, then point left pointer to NULL
// convert left subtrree recursively
}

{
// Base Case
return;

//traverse over the linked list in level order traversal fashion
queue<node*> q;
//first node of min heap will be smallest element
//i.e. first element of inorder traversal
// point head to next node
root->right = NULL;
// insert into queue
q.push(root);
{
node* nodeAtFront = q.front();
q.pop();
// now remove one node from linked list and make left child
// if there are more nodes make a right child
// push them into queue
leftNode->right = NULL;
nodeAtFront->left = leftNode;
q.push(leftNode);
// similarly do the same for right child if it exists
rightNode->right = NULL;
nodeAtFront->right = rightNode;
q.push(rightNode);
}
}
}

// Function to convert BST into a Min-Heap
// without using any extra space
node* BSTToMinHeap(node* &root)
{
// now set the root for min heap
root = NULL;
// convert the linked list into min heap
}

int main()
{

node* root = create(5);
root->left = create(4);
root->right = create(6);
root->left->left = create(2);
root->left->right = create(3);

BSTToMinHeap(root);

levelOrderTraversal(root);

return 0;
}
```
```2
4 3
5 6
```

### Java code to Convert BST into a Min-Heap without using array

```import java.util.*;
import java.lang.*;
import java.io.*;

class node{
int data;
node left;
node right;
}

class Tree{
static node root;
static node create(int data){
node tmp = new node();
tmp.data = data;
tmp.left = null;
tmp.right = null;
return tmp;
}

static void levelOrderTraversal(node root)
{
if (root == null) return;
while(!q.isEmpty()){
int qSize = q.size();
while(qSize-- > 0){
node nodeAtFront = q.peek();
q.remove();
if(nodeAtFront.left != null)
if(nodeAtFront.right != null)
System.out.print(nodeAtFront.data+" ");
}
System.out.println();
}
}

{
if(root == null)

//first convert right subtree into linked list
// insert root into the linked list
//if head pointer exists, then point left pointer to NULL
// convert left subtrree recursively

}

{
// Base Case
return null;

//traverse over the linked list in level order traversal fashion
//first node of min heap will be smallest element
//i.e. first element of inorder traversal
// point head to next node
root.right = null;
// insert into queue
{
node nodeAtFront = q.peek();
q.remove();
// now remove one node from linked list and make left child
// if there are more nodes make a right child
// push them into queue
leftNode.right = null;
nodeAtFront.left = leftNode;
// similarly do the same for right child if it exists
rightNode.right = null;
nodeAtFront.right = rightNode;
}
}
return root;
}

// Function to convert BST into a Min-Heap
// without using any extra space
static node BSTToMinHeap(node root)
{
// now set the root for min heap
root = null;
// convert the linked list into min heap
return root;
}

public static void main(String[] args)
{

node root = create(5);
root.left = create(4);
root.right = create(6);
root.left.left = create(2);
root.left.right = create(3);

root = BSTToMinHeap(root);

levelOrderTraversal(root);
}

}```
```2
4 3
5 6
```

## Complexity Analysis

### Time Complexity

O(N), because we have first converted the tree into a linked list and then id a level order traversal. Both pf which are liner time complexity operation. Thus a linear time complexity is achieved.

READ  Binary Tree zigzag level order Traversal

### Space Complexity

O(log N), because we have used a queue to store the children in a single level. This takes logarithmic space complexity. But the algorithm itself works in place.

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions