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