Binary Tree: Convert BST to Max Heap

Problem Statement:

Convert a BST into Max Heap.

Max Heap property:

All the values in the left sub tree of a node should be less than the value in the right subtree.

Example:

Input: 

    /*
     *           4
     *         /    \
     *        2      6
     *       / \    /  \
     *      1   3  5    7
     */

Output:

    /*
     *           7
     *         /    \
     *        3      6
     *       / \    /  \
     *      1   2  4    5
     */

Solution Explanation:

Take an temp array and insert node into the temp array in in-order traversal.

Then perform post order traversal of the tree, copy the elements from the array into the tree node to get the result

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

Code Solution

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

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_postorder(Node* root)
{
    if (root == NULL)
        return;

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

}


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

void insert_PostOrder(Node* root, vector<int>& nodes, int& index) 
{
    if (root == nullptr) 
    {
        return;
    }

    insert_PostOrder(root->left, nodes, index);  
    insert_PostOrder(root->right, nodes, index);

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

}

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

    insert_inorder(root, nodes);

    int index = 0;

    insert_PostOrder(root, nodes, index);
}

int main(void)
{
    /*
     *           4
     *         /    \
     *        2      6
     *       / \    /  \
     *      1   3  5    7
     */
    struct Node* root = newNode(4);
    root->left = newNode(2);
    root->right = newNode(6);
    root->left->left = newNode(1);
    root->left->right = newNode(3);
    root->right->left = newNode(5);
    root->right->right = newNode(7);

    solution(root);
    
    cout << "Postorder traversal : ";
    display_postorder(root);

    return 0;
}

Output

Postorder traversal : 1 2 3 4 5 6 7