Heap: Given a BST, convert into Min Heap

Problem Statement:

Given a BST that is a complete binary tree, you need to convert into Min Heap.

What is a BST ?

A binary tree that satisfies below condition is called as BST:

1. All Nodes in the left sub tree will have values strictly less than the node’s value.

2. All the nodes in the right subtree if a node values strictly greater than the nodes value.

What is a Min Heap?

In Min Heap, the values in all the left subtree of the node should be less then all the values in the right subtree of the node.

Example:

Solution Explanation:

You need to create an array of size equal to the number of nodes in the given BST.

Perform inorder traversal of the BST and copy into the array in sorted order.

Perform preorder traversal of the tree and add the elements into the tree forming Special Max Heap.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Node 
{
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) 
    {
        data = val;
        left = right = NULL;
    }
};


void fillInorder(Node* root, vector<int>& arr) 
{
    if (root == nullptr) {
        return;
    }
  
    fillInorder(root->left, arr);  
    arr.push_back(root->data);          
    fillInorder(root->right, arr); 
}

void fillPreorder(Node* root, vector<int>& inorderArr, int& index) 
{
    if (root == NULL) 
    {
        return;
    }

    root->data = inorderArr[index++];

    fillPreorder(root->left, inorderArr, index);  
    fillPreorder(root->right, inorderArr, index);
}

void solution(Node* root) 
{
  
    vector<int> inorderArr;

    fillInorder(root, inorderArr);

    int index = 0;

    fillPreorder(root, inorderArr, index);
}

void displayPreorder(Node* root) 
{
    if (root == nullptr) 
    {
        return;
    }

    cout << root->data << " "; 
    displayPreorder(root->left); 
    displayPreorder(root->right); 
}

int main() {
  
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    solution(root);
    displayPreorder(root);

    return 0;
}

Output

4 2 5 1 6 3 7