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);
arr.add(root.data);
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