Problem Statement:
You are given two balanced BST, you need to merge the two given balanced BST.
Solution
THe solution is very simple.
WKT in-order traversal of BST will give the sorted order.
So we need to perform in-order traversal of both BST, we will get two sorted arrays.
Then we need to merge two arrays by using merge sort to merge 2 arrays and return as result.
Solution in C++
#include<iostream>
#include<vector>
#include<string>
#include<set>
using namespace std;
struct Node
{
int data;
struct Node *left, *right;
};
Node *get_new_node(int item)
{
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
Node* insert_into_bst(Node* node, int data)
{
if (node == NULL) return get_new_node(data);
if (data < node->data)
node->left = insert_into_bst(node->left, data);
else if (data > node->data)
node->right = insert_into_bst(node->right, data);
return node;
}
void print_inorder(Node* Node)
{
if (Node == NULL)
return;
print_inorder(Node->left);
cout<<" "<<Node->data;
print_inorder(Node->right);
}
Node* build_tree(vector<struct Node*> &nodes, int start, int end)
{
// base case
if (start > end)
return NULL;
int mid = (start + end)/2;
Node *root = nodes[mid];
root->left = build_tree(nodes, start, mid-1);
root->right = build_tree(nodes, mid+1, end);
return root;
}
void store_in_order(Node *root, vector<int> &arr)
{
if (root != NULL) {
store_in_order(root->left, arr);
arr.push_back(root->data);
store_in_order(root->right, arr);
}
}
vector<int> merge_sort_arrays(vector<int> &arr1, vector<int> &arr2)
{
int i = 0, j = 0;
vector<int> arr;
while (i < arr1.size() && j < arr2.size()) {
if (arr1[i] < arr2[j]) {
arr.push_back(arr1[i]);
i++;
} else {
arr.push_back(arr2[j]);
j++;
}
}
while (i < arr1.size()) {
arr.push_back(arr1[i]);
i++;
}
while (j < arr2.size()) {
arr.push_back(arr2[j]);
j++;
}
return arr;
}
Node* construct_BST_from_sorted_array(vector<int> &arr, int start, int end)
{
// base case
if (start > end)
{
return NULL;
}
int mid = (start + end) / 2;
Node *root = get_new_node(arr[mid]);
root->left = construct_BST_from_sorted_array(arr, start, mid - 1);
root->right = construct_BST_from_sorted_array(arr, mid + 1, end);
return root;
}
Node* merge_BST(Node *root1, Node *root2)
{
vector<int> arr1;
store_in_order(root1, arr1);
vector<int> arr2;
store_in_order(root2, arr2);
vector<int> arr = merge_sort_arrays(arr1, arr2);
return construct_BST_from_sorted_array(arr, 0, arr.size() - 1);
}
int main()
{
Node *root_1 = NULL;
root_1 = insert_into_bst(root_1, 1);
insert_into_bst(root_1, 2);
insert_into_bst(root_1, 3);
insert_into_bst(root_1, 4);
insert_into_bst(root_1, 5);
Node *root_2 = NULL;
root_2 = insert_into_bst(root_2, 6);
insert_into_bst(root_2, 7);
insert_into_bst(root_2, 8);
insert_into_bst(root_2, 9);
insert_into_bst(root_2, 10);
Node *root = merge_BST(root_1, root_2);
cout<<"The in-order traversal of merged trees ";
print_inorder(root);
return 0;
}
Output:
The in-order traversal of merged trees 1 2 3 4 5 6 7 8 9 1