Do you think IIT Guwahati certified course can help you in your career?
Introduction
In this blog, we will solve the problem of converting a given Binary Search Tree to a Min Heap. The task is relatively simple if we have the required knowledge of data structures.
First, we need to look at the pre-requisites required to solve this problem.
Pre-requisite
A Heap data structure is a special kind of binary tree that meets the following two conditions:
Complete Binary Tree - All levels except the last level are filled completely in a CBT, and the last level is filled from left to right.
Heap-order property - According to the heap-order property for a Min Heap, the value of each node should be less than or equal to the value of its child nodes, and the minimum element should always be at the top of the tree.
An inorder traversal is a binary tree traversal algorithm that visits the left subtree, then the root and then finally the right subtree.
A preorder traversal is a binary tree traversal algorithm that visits the root, then the left subtree and then finally the right subtree.
Problem Statement
You will be given a binary search tree and you need to convert that binary search tree into a min heap.
Example
Input
Output
Preorder Traversal = {1, 4, 5, 6, 7, 8, 10}
Explanation
First store an inorder traversal for the input and then overwrite the BST data with the values from the array in a preorder traversal manner which makes the output as a min heap. We can see that the values in the left subtrees are less than the values in the right subtree.
Approach
This program converts a given Binary Search Tree (BST) into a Min Heap. The BST is first traversed in an inorder manner to obtain the nodes in sorted order. Then, the sorted nodes are assigned to the BST in a preorder manner to obtain a Min Heap. The program uses an iterative approach for both inorder and preorder traversals, as well as conversion.
Algorithm
A function 'getInorder' is called that takes a pointer to the root node and a vector 'arr' as parameters. This function performs an iterative inorder traversal of the binary search tree and stores the node values in the vector 'arr'.
A function 'getPreorder' is called that takes a pointer to the root node as a parameter. This function performs an iterative preorder traversal of the binary tree and prints the node values.
We implement a function called 'BSTToMinHeaphelper' that takes a pointer to the root node and a vector 'arr' as parameters.
This function performs an iterative traversal of the binary tree and replaces the data of each node with the values stored in the vector 'arr' in a manner that converts the binary search tree into a min-heap.
Finally, a function called 'MinHeap' that takes a pointer to the root node as a parameter.
This function creates an empty vector 'arr', performs an inorder traversal of the binary search tree using the 'inorderTraversal' function, and stores the node values in the vector 'arr'.
It then converts the binary search tree into a min-heap using the 'BSTToMinHeaphelper' function.
Now, convert the binary search tree into a min-heap using the 'MinHeap' function.
Print the preorder traversal of the min-heap using the 'getPreorder' function.
Dry Run
1. First, create the BST using the ‘node()’ function.
2. Next, we call the ‘MinHeap()’ function which performs the following steps:
a. Calls the ‘getInorder()’ function to get the inorder traversal of the BST. This function uses an iterative approach with a stack to traverse the tree in inorder and store the node values in a vector ‘arr’. The inorder traversal of the binary search tree is.
b. Calls the ‘BSTToMinHeaphelper()’ function with the root node of the BST and ‘arr’.
First it initializes a stack ‘s’ and the root element is pushed into the stack. While the stack is not empty we pop the top element and push the right child followed by the left child into the stack. Also initialize i=0 which corresponds to the first element of the array ‘arr’.
Here, the root is 6. We push 6 into the stack.
Now pop the top element ‘curr’ from the stack which is 6 and the data of ‘curr’ is updated with the next element in the array ‘arr’. The new tree looks like this:
Now we push the right child and the left child of root, i.e., 8 and 4.
We pop 4 which is the top element in this case and update with the next element in the array ‘arr’.
The new tree looks like this:
Now we push the right and left child of 4 which are 5 and 1 into the stack.
We pop 1 which is the top element in this case and update with the next element in the array ‘arr’.
The new tree looks like this:
As there is no left and right child of 1. Therefore we do not push anything to stack.
Now we pop the top element 5 in this case and update with the next element in the array ‘arr’.
The new tree looks like this
As there is no left and right child of 5. Therefore we do not push anything to stack.
Now we pop the top element 8 in this case and update with the next element in the array ‘arr’.
The new tree looks like this
Now we push the right and left child of 8 which are 10 and 7 into the stack.
Now we pop the top element 7 in this case and update with the next element in the array ‘arr’.
The new tree looks like this
As there is no left and right child of 7. Therefore we do not push anything to stack.
Now we pop the top element 10 in this case and update with the next element in the array ‘arr’.
The new tree looks like this
The stack is empty now we come out of the while loop and print the preorder traversal of the updated tree.
3. Finally, we call the ‘getPreorder()’ function to print the preorder traversal of the converted min-heap. This function uses an iterative approach with a stack to traverse the tree in a preorder traversal and print the node values.
Code in C++
#include <bits/stdc++.h>
using namespace std;
// Structure of node
struct Node {
int data;
Node *left, *right;
};
struct Node* node(int data) {
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Iterative Inorder Traversal
void getInorder(Node* root, vector<int>& arr) {
// Initialize a stack to perform inorder traversal
stack<Node*> s;
Node* curr = root;
/*
Print the left subtree followed
by the root and finally the right subtree
*/
while (curr != NULL || !s.empty()) {
while (curr != NULL) {
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
arr.push_back(curr->data);
curr = curr->right;
}
}
// Iterative Preorder Traversal
void getPreorder(Node* root) {
// Base case
if (root == NULL) {
return;
}
// Initialize a stack to perform preorder traversal
stack<Node*> s;
s.push(root);
/*
Print the root followed by the left
subtree and finally the right subtree
*/
while (!s.empty()) {
Node* curr = s.top();
s.pop();
cout << curr->data << " ";
if (curr->right) {
s.push(curr->right);
}
if (curr->left) {
s.push(curr->left);
}
}
}
/*
Function to convert a binary
search tree to a min heap
*/
void BSTToMinHeaphelper(Node* root, vector<int> arr) {
stack<Node*> s;
/*
Start with pushing the
root node to the stack
*/
s.push(root);
int i = 0;
while (!s.empty()) {
Node* curr = s.top();
s.pop();
/*
Update the data of the current node
with the next element from the sorted array
*/
curr->data = arr[i++];
// push the right child
if (curr->right != NULL) {
s.push(curr->right);
}
// push the left child
if (curr->left != NULL) {
s.push(curr->left);
}
}
}
void MinHeap(Node* root) {
vector<int> arr;
// Store the inorder traversal in the array
getInorder(root, arr);
/*
Convert the binary search tree to a min
heap in an iterative manner
*/
BSTToMinHeaphelper(root, arr);
}
int main() {
struct Node* root = node(6);
root->left = node(4);
root->right = node(8);
root->left->left = node(1);
root->left->right = node(5);
root->right->left = node(7);
root->right->right = node(10);
MinHeap(root);
cout << "Preorder Traversal:" << endl;
/*
Call the function and
print the preorder traversal
*/
getPreorder(root);
return 0;
}
You can also try this code with Online C++ Compiler
from typing import List
# Structure of node
class Node:
def __init__(self, data: int):
self.data = data
self.left = None
self.right = None
def node(data: int) -> Node:
newNode = Node(data)
newNode.left = None
newNode.right = None
return newNode
# Iterative Inorder Traversal
def getInorder(root: Node, arr: List[int]) -> None:
# Initialize a stack to perform inorder traversal
s = []
curr = root
# Print the left subtree followed
# by the root and finally the right subtree
while curr is not None or s:
while curr is not None:
s.append(curr)
curr = curr.left
curr = s.pop()
arr.append(curr.data)
curr = curr.right
# Iterative Preorder Traversal
def getPreorder(root: Node) -> None:
if root is None:
return
# Initialize a stack to perform preorder traversal
s = []
s.append(root)
# Print the root followed by the left
# subtree and finally the right subtree
while s:
curr = s.pop()
print(curr.data, end=" ")
if curr.right is not None:
s.append(curr.right)
if curr.left is not None:
s.append(curr.left)
print()
# Function to convert a binary
# search tree to a min heap
def BSTToMinHeaphelper(root: Node, arr: List[int]) -> None:
s = []
# Start with pushing the
# root node to the stack
s.append(root)
i = 0
while s:
curr = s.pop()
# Update the data of the current node
# with the next element from the sorted array
curr.data = arr[i]
i += 1
# Push the right child
if curr.right is not None:
s.append(curr.right)
# Push the left child
if curr.left is not None:
s.append(curr.left)
def MinHeap(root: Node) -> None:
arr = []
# Store the inorder traversal in the array
getInorder(root, arr)
# Convert the binary search tree to a min
# heap in an iterative manner
BSTToMinHeaphelper(root, arr)
if __name__ == "__main__":
root = node(6)
root.left = node(4)
root.right = node(8)
root.left.left = node(1)
root.left.right = node(5)
root.right.left = node(7)
root.right.right = node(10)
MinHeap(root)
# Call the function and
# print the preorder traversal
print("Preorder Traversal:")
getPreorder(root)
You can also try this code with Online Python Compiler
The time complexity is O(N), where ‘N’ gives the number of nodes in the binary search tree. This is because we perform an inorder traversal of the binary search tree, which takes O(N) time, and then we perform an iterative traversal of the binary tree to convert it to a min-heap, which takes another O(N) time.
Space Complexity
The space complexity is O(H), where ‘H’ represents the height of the binary tree. This is because we use a stack to perform the iterative traversals, and the maximum size of the stack is equal to the height of the binary tree.
Frequently Asked Questions
What do you mean by complete binary tree?
A binary tree where all levels except the last level are filled completely, and the last level is filled from left to right is called a complete binary tree.
What is the heap order property?
The heap order property states that the value of every node in the tree must be greater than or lesser than (depending on the type of the heap) the value of both of its children.
What are the necessary conditions for a binary tree to be called a Heap?
If a Binary Tree satisfies these two conditions, First, the binary tree should be a Complete Binary Tree and the binary tree should have the heap-order property.
What is the difference between a Min Heap and a Max Heap?
The only difference between a Min Heap and a Max Heap is the heap-ordering property. In the case of a min-heap, the minimum element is always at the top of the tree, and the value of each node is less than the value of both of its children, whereas in the case of a max heap the value of every node is greater than its children and maximum element is at the top of the tree.
What is the difference between inorder traversal and preorder traversal?
Preorder traversal visits the root node first, then the left subtree and then finally the right subtree, while inorder traversal visits the left subtree first, followed by the root node, and then the right subtree.
Conclusion
In this blog, we learned how to convert a BST to a min heap. We have implemented the problem in C++ and python programming languages.
For more Tree data structure articles, you can refer following links:
84+ registered