Convert BST to Max Heap in C++

In this tutorial, we will be discussing a program to convert a binary search tree to a max heap.

For this we will be provided with a binary search tree. Our task is to convert the given binary search tree into a max heap such that following the condition of the binary search tree when elements are compared with themselves.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; //node structure of BST struct Node {    int data;    Node *left, *right; }; //node creation struct Node* getNode(int data) {    struct Node* newNode = new Node;    newNode->data = data;    newNode->left = newNode->right = NULL;    return newNode; } //performing post order traversal void postorderTraversal(Node*); //moving in a sorted manner using inorder traversal 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 convert_BSTHeap(Node* root, vector<int> arr, int* i){    if (root == NULL)       return;    convert_BSTHeap(root->left, arr, i);    convert_BSTHeap(root->right, arr, i);    //copying data from array to node    root->data = arr[++*i]; } //converting to max heap void convert_maxheap(Node* root) {    vector<int> arr;    int i = -1;    inorderTraversal(root, arr);    convert_BSTHeap(root, arr, &i); } //printing post order traversal void postorderTraversal(Node* root) {    if (!root)       return;    postorderTraversal(root->left);    postorderTraversal(root->right);    cout << root->data << " "; } int main() {    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);    convert_maxheap(root);    cout << "Postorder Traversal:" << endl;    postorderTraversal(root);    return 0; }

Output

Postorder Traversal: 1 2 3 4 5 6 7