1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Linked list and Level Order Traversal Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
3.1.
What is level order traversal in a binary tree?
3.2.
What is the height of the tree?
3.3.
What is the level in a binary tree?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# BST into a Min-Heap Without Using Array

## Introduction

In the hidden village of leaf, you are a part of team 7. Your sensei Kakashi Hatake and your two comrades had given you a task. You are supposed to convert a BST into a min-heap. But the constraint is you can’t use an array. Now it's up to you, the leader of team 7, to figure out how to do it.

Converting BST into a min-heap without an array is a frequently asked problem in a tech interview. You will also find it in DSA sheets quite popular these days. It is advised to practice such problems during preparation. So let’s start our discussion by converting BST into a min-heap without further ado.

### Problem Statement

The "Convert BST into a Min Heap without Using an Array" problem asks you to take BST (binary search tree) as an input. And then convert it into a min-heap. The min-heap should contain all of the binary search tree's elements. We are not supposed to use an array in our approach.

Let’s understand the problem of conversion of BST into a min-heap by some examples.

### Sample Examples

Example 1: Given BST

Output: Min Heap

## Linked list and Level Order Traversal Approach

We will use a linked list and level order traversal approach to convert BST into a min-heap. Here, we first convert the tree into a linked list. And then we do a level order traversal.

Now let’s see the algorithm to convert BST into a min-heap.

### Algorithm

1. Make a data structure to store a binary tree node.

2. Now make a recursive function to insert a key into the BST. We'll follow three cases in it:
• If the root value is null, create a new node and return it.
• If the given key value is less than the root node, go for the left subtree.
• And if the given key value is more than the root node, go for the right subtree.

3. Make a helper function to perform level order traversal on a binary tree.

4. Now we have to create a function to construct a complete binary tree from sorted keys in a queue.

5. Construct a queue to store the value of the parent nodes.

6. Initialize the root node of the binary tree, enqueue root node, and loop till all keys are processed.

7. Now create a function to perform in-order traversal on a given binary tree and enqueue all nodes (in encountered order).

8. Maintain a queue to store in order traversal on the tree. Fill the queue in an in-order fashion, and construct a complete binary tree from sorted keys in the queue.

### Implementation in C++

``````#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <utility>
using namespace std;

// The data structure to store a binary tree node
struct Node
{
int data;
Node* left = nullptr, *right = nullptr;

Node() {}
Node(int data): data(data) {}
};

// Now the recursive function to insert a key into a BST
Node* insert(Node* root, int key)
{
//Now the root is null. create a new node and return
if (root == nullptr) {
return new Node(key);
}

// Now if the given key is less than the root node, recurr for left subtree
if (key < root->data) {
root->left = insert(root->left, key);
}

// Now if the given key is more than the root node, recur for the right subtree
else {
root->right = insert(root->right, key);
}

return root;
}

// The helper function to perform level order traversal on a binary tree
void printLevelOrderTraversal(Node* root)
{
// For base case: empty tree
if (root == nullptr) {
return;
}

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

while (!q.empty())
{
int n = q.size();
while (n--)
{
Node* front = q.front();
q.pop();

cout << front->data << ' ';

if (front->left) {
q.push(front->left);
}

if (front->right) {
q.push(front->right);
}
}

cout << endl;
}
}

// Now, Function to construct a complete binary tree from sorted keys in a queue
Node* construct(queue<int> &keys)
{
// To construct a queue to store the parent nodes
queue<Node*> q;

// Now initialize the root node of the complete binary tree
Node* root = new Node(keys.front());
keys.pop();

// To enqueue root node
q.push(root);

// Now loop till all keys are processed
while (!keys.empty())
{
// To dequeue front node
Node* parent = q.front();
q.pop();

// To allocate the left child of the parent node with the next key
parent->left = new Node(keys.front());
keys.pop();

// to enqueue left child node
q.push(parent->left);

// now if the next key exists
if (!keys.empty())
{
// now allocate the right child of the parent node with the next key
parent->right = new Node(keys.front());
keys.pop();

// to enqueue right child node
q.push(parent->right);
}
}

// now return the root node of the complete binary tree
return root;
}

// the function to perform inorder traversal on a given binary tree and
// enqueue all nodes (in encountered order)
void inorder(Node* root, queue<int> &keys)
{
if (root == nullptr) {
return;
}

inorder(root->left, keys);
keys.push(root->data);
inorder(root->right, keys);
}

// Function to convert a BST into a min heap without using
// any auxiliary space
void convert(Node* &root)
{
// The base case
if (root == nullptr) {
return;
}

// Now maintain a queue to store inorder traversal on the tree
queue<int> keys;

// Now fill the queue in an inorder fashion
inorder(root, keys);

// Now construct a complete binary tree from the sorted keys in the queue
root = construct(keys);
}

int main()
{
vector<int> keys = { 3, 2,5, 4, 8, 10 };

Node* root = nullptr;
for (int key: keys) {
root = insert(root, key);
}

convert(root);
printLevelOrderTraversal(root);

return 0;
}``````

Output:

#### Time Complexity

The time complexity of the above approach is O(n). It is because we first converted the tree into a linked list. And then, we did a level order traversal. The two operations used are linear time operations. That is why the time complexity of the approach is O(n).

#### Space Complexity

The space complexity of the above approach is O(log n). As we used a queue to store the children on a single level. Log space complexity is required. So, the algorithm works in place.

### What is level order traversal in a binary tree?

We visit all the nodes of a previous level before going on to the next level in level order traversal. Because we cover the breadth of a tree first in level order traversal, it's also known as the Breadth-First search.

### What is the height of the tree?

The height of a tree is determined by the number of edges connecting the root node to the leaf node along the longest path.

### What is the level in a binary tree?

The root node is the topmost node in a binary tree. The number of edges along the path between a node and the root node determines its level.

## Conclusion

This article briefly discussed the problem of converting BST into a min-heap without using an array. We used a linked list and level order traversal approach to do the conversion.

We hope that this blog had helped you enhance your knowledge about the above question and if you like to learn more, check out our articles Level Order Traversal Of  A Binary TreePrint the node values at odd levels of a Binary treeReplace each node in a binary tree with a sum of its in order predecessor and successor, and Print Nodes between two given Level Numbers of a Binary Tree. You can also refer to our guided path on the basics of java and many more on our Website.

Recommended Problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, and many more! If you wish to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy learning!

Live masterclass