Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Pre-requisite
3.
Problem Statement
3.1.
Example 
4.
Approach
5.
Algorithm
5.1.
Dry Run
5.2.
Code in C++
5.3.
Code in Python
5.4.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What do you mean by complete binary tree?
6.2.
What is the heap order property?
6.3.
What are the necessary conditions for a binary tree to be called a Heap?
6.4.
What is the difference between a Min Heap and a Max Heap?
6.5.
What is the difference between inorder traversal and preorder traversal?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Converting a BST to Min Heap

Author Rishabh
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

intro image

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.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 

input image

Output

Preorder Traversal = {1, 4, 5, 6, 7, 8, 10}

output image

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

  1. 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'.
     
  2. 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.
     
  3. We implement a function called 'BSTToMinHeaphelper' that takes a pointer to the root node and a vector 'arr' as parameters.
     
  4. 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.
     
  5. Finally, a function called 'MinHeap' that takes a pointer to the root node as a parameter. 
     
  6. 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'.
     
  7. It then converts the binary search tree into a min-heap using the 'BSTToMinHeaphelper' function.
     
  8. Now, convert the binary search tree into a min-heap using the 'MinHeap' function.
     
  9. Print the preorder traversal of the min-heap using the 'getPreorder' function.

Dry Run

1. First, create the BST using the ‘node()’ function.

dry run 1

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.

dry run 2

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’.
dry run 3
  • Here, the root is 6. We push 6 into the stack.
dry run 4
  • 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:
dry run 5
  • Now we push the right child and the left child of root, i.e., 8 and 4.
dry run 6
  • We pop 4 which is the top element in this case and update with the next element in the array ‘arr’.
dry run 7
  •  The new tree looks like this:
dry run 8
  • Now we push the right and left child of 4 which are 5 and 1 into the stack.
dry run 9
  • We pop 1 which is the top element in this case and update with the next element in the array ‘arr’. 
dry run 10
  • The new tree looks like this:
dry run 11
  • As there is no left and right child of 1. Therefore we do not push anything to stack.
dry run 12
  • Now we pop the top element 5 in this case and update with the next element in the array ‘arr’. 
dry run 13
  • The new tree looks like this
dry run 14
  • As there is no left and right child of 5. Therefore we do not push anything to stack.
dry run 15
  • Now we pop the top element 8 in this case and update with the next element in the array ‘arr’. 
dry run 16
  • The new tree looks like this
dry run 17
  • Now we push the right and left child of 8 which are 10 and 7 into the stack.
dry run 18
  • Now we pop the top element 7 in this case and update with the next element in the array ‘arr’. 
dry run 19
  • The new tree looks like this
dry run 20
  • As there is no left and right child of 7. Therefore we do not push anything to stack.
dry run 21
  • Now we pop the top element 10 in this case and update with the next element in the array ‘arr’. 
dry run 22
  • The new tree looks like this
dry run 23
  • 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.

dry run 24

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;
}


Output

output 1

Code in Python

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)


Output

output 2

Complexity Analysis

Time Complexity

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:

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enrol in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Priority Queue Using a Linked List
Next article
N Max Pair Combinations
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass