-
Notifications
You must be signed in to change notification settings - Fork 27
/
Binary Tree to BST.cpp
40 lines (40 loc) · 1.03 KB
/
Binary Tree to BST.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
class Solution{
public:
void getArr(int arr[], int *index, Node *root)
{
if(root == NULL)
return ;
getArr(arr, index, root->left);
arr[*index] = root->data;
*index += 1;
getArr(arr, index, root->right);
}
void convert(Node *root, int arr[], int *index)
{
if(root == NULL)
return ;
convert(root->left, arr, index);
root->data = arr[*index];
*index += 1;
convert(root->right, arr, index);
}
int totalNodes(Node* root)
{
if(root == NULL)
return 0;
return (1 + totalNodes(root->left) + totalNodes(root->right));
}
Node* binaryTreeToBST (Node *root)
{
if(root == NULL)
return NULL ;
int n = totalNodes(root);
int *arr = new int[n + 1];
int index = 0;
getArr(arr, &index, root);
sort(arr, arr + index);
index = 0;
convert(root, arr, &index);
return root;
}
};