-
Notifications
You must be signed in to change notification settings - Fork 2
/
BST_to_min_heap.cpp
111 lines (90 loc) · 2.43 KB
/
BST_to_min_heap.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
// structure of a node of BST
struct Node
{
int data;
Node *left, *right;
};
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct Node* getNode(int data)
{
struct Node *newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// function prototype for preorder traversal
// of the given tree
void preorderTraversal(Node*);
// function for the inorder traversal of the tree
// so as to store the node values in 'arr' in
// sorted order
void inorderTraversal(Node *root, vector<int>& arr)
{
if (root == NULL)
return;
// first recur on left subtree
inorderTraversal(root->left, arr);
// then copy the data of the node
arr.push_back(root->data);
// now recur for right subtree
inorderTraversal(root->right, arr);
}
// function to convert the given BST to MIN HEAP
// performs preorder traversal of the tree
void BSTToMinHeap(Node *root, vector<int> arr, int *i)
{
if (root == NULL)
return;
// first copy data at index 'i' of 'arr' to
// the node
root->data = arr[++*i];
// then recur on left subtree
BSTToMinHeap(root->left, arr, i);
// now recur on right subtree
BSTToMinHeap(root->right, arr, i);
}
// utility function to convert the given BST to
// MIN HEAP
void convertToMinHeapUtil(Node *root)
{
// vector to store the data of all the
// nodes of the BST
vector<int> arr;
int i = -1;
// inorder traversal to populate 'arr'
inorderTraversal(root, arr);
// BST to MIN HEAP conversion
BSTToMinHeap(root, arr, &i);
}
// function for the preorder traversal of the tree
void preorderTraversal(Node *root)
{
if (!root)
return;
// first print the root's data
cout << root->data << " ";
// then recur on left subtree
preorderTraversal(root->left);
// now recur on right subtree
preorderTraversal(root->right);
}
// Driver program to test above
int main()
{
// BST formation
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);
convertToMinHeapUtil(root);
cout << "Preorder Traversal:" << endl;
preorderTraversal(root);
return 0;
}