Binary Search Trees: Merge Two balanced BST

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