#include <bits/stdc++.h>
using namespace std;
// tree node is defined
class TreeNode
{
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
val = data;
left = NULL;
right = NULL;
}
};
// level order traversal for BST
void levelorder(TreeNode *root)
{
if (!root)
return;
queue<TreeNode *> q;
q.push(root);
q.push(NULL);
int count = 1;
cout << "Start of level: " << count << endl;
while (!q.empty())
{
TreeNode *temp = q.front();
q.pop();
if (temp == NULL)
{
if (!q.empty())
{
q.push(NULL);
cout << "\nEnd of level: " << count << endl;
count++;
cout << "Start of level: " << count << endl;
}
else
{
cout << "\nEnd of level: " << count << endl;
}
}
else
{
cout << temp->val << " ";
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
}
}
// storing the inorder traversal
void inorder(TreeNode *root, vector<int> &store)
{
if (!root)
return;
inorder(root->left, store);
store.push_back(root->val);
inorder(root->right, store);
}
// convert to min heap from BST
TreeNode *convertToMinHeap(vector<int> &store)
{
int index = 0;
TreeNode *root = new TreeNode(store[index++]);
queue<TreeNode *> q;
q.push(root);
// insert level wise
while (!q.empty())
{
TreeNode *temp = q.front();
q.pop();
if (index == store.size())
return root;
// first insert as left child
temp->left = new TreeNode(store[index++]);
q.push(temp->left);
if (index == store.size())
return root;
// then insert as right child
temp->right = new TreeNode(store[index++]);
q.push(temp->right);
}
return root;
}
int main()
{
// below is the unbalanced BST as per example
TreeNode *root = new TreeNode(15);
root->left = new TreeNode(10);
root->right = new TreeNode(20);
root->left->right = new TreeNode(13);
root->right->right = new TreeNode(23);
cout << "Level order traversal of the BST:\n";
levelorder(root);
cout << "Converting the BST into min heap\n";
vector<int> store;
inorder(root, store);
TreeNode *heap = convertToMinHeap(store);
cout << "Converted into a min heap...\n";
cout << "Level order traversal of the min heap is :\n";
levelorder(heap);
return 0;
}
Output
Level order traversal of the BST:
Start of level: 1
15
End of level: 1
Start of level: 2
10 20
End of level: 2
Start of level: 3
13 23
End of level: 3
Converting the BST into min heap
Converted into a min heap...
Level order traversal of the min heap is :
Start of level: 1
10
End of level: 1
Start of level: 2
13 15
End of level: 2
Start of level: 3
20 23
End of level: 3
0 Comments