-
Notifications
You must be signed in to change notification settings - Fork 0
/
BT2BST.cpp
98 lines (79 loc) · 2.39 KB
/
BT2BST.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
//Convert a given binary tree to BST (Binary Search Tree) by keeping original structure of the binary tree intact.
/*The idea is to traverse the Binary Tree and store its keys in a set. We know that an in-order traversal of a binary search tree returns the nodes in sorted order,
so we traverse the tree again in in-order fashion and put back the keys present in set (in sorted order) back to their correct position in BST.
<p>The advantage of using set over vector/array is that the keys are always retrieved in sorted order from set. If we use vector/array,
we have to sort the keys first before inserting them back*/
#include <iostream>
#include <set>
using namespace std;
// Data structure to store a Binary Search Tree node
struct Node {
int data;
Node *left, *right;
};
// Function to create a new binary tree node having given key
Node* newNode(int key)
{
Node* node = new Node;
node->data = key;
node->left = node->right = nullptr;
return node;
}
// Function to perform in-order traversal of the tree
void inorder(Node* root)
{
if (root == nullptr)
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
// Function to traverse the binary tree and store its keys in a set
void extractKeys(Node *root, auto &set)
{
// base case
if (root == nullptr)
return;
extractKeys(root->left, set);
set.insert(root->data);
extractKeys(root->right, set);
}
// Function to put back keys in set in their correct order in BST
// by doing in-order traversal
void convertToBST(Node *root, auto &it)
{
if (root == nullptr)
return;
convertToBST(root->left, it);
root->data = *it;
it++;
convertToBST(root->right, it);
}
// main function
int main()
{
/* Construct below tree
8
/ \
/ \
3 5
/ \ / \
/ \ / \
10 2 4 6 */
Node* root = newNode(8);
root->left = newNode(3);
root->right = newNode(5);
root->left->left = newNode(10);
root->left->right = newNode(2);
root->right->left = newNode(4);
root->right->right = newNode(6);
// traverse the binary tree and store its keys in a set
set<int> set;
extractKeys(root, set);
// put back keys present in set in their correct order in BST
auto it = set.begin();
convertToBST(root, it);
// print the BST
inorder(root);
return 0;
}