Approach 1: Using Vector

• Time Complexity :- O(n+m)

• Space Complexity :- O(n+m)

• Self-explanatory Code:-

    void inorder(TreeNode<int> *root, vector<int> &in){
        if(root == NULL){
            return;
        }
  
        inorder(root->left, in);
        in.push_back(root->data);
        inorder(root->right, in);
    }
  
    vector<int> merge(vector<int> &a, vector<int> &b){
        vector<int> ans(a.size() + b.size());
  
        int i=0, j=0, k=0;
        while(i<a.size() && j<b.size()){
            if(a[i]<b[j]){
                ans[k++] = a[i];
                i++;
            }
            else{
                ans[k++] = b[j];
                j++;
            }
        }
  
        while(i<a.size()){
            ans[k++] = a[i];
            i++;
        }
  
        while(j<b.size()){
            ans[k++] = b[j];
            j++;
        }
  
        return ans;
    }
  
    TreeNode<int>*intoBST(vector<int> &m, int s, int e){
        if(s>e){
            return NULL;
        }
  
        int mid = (s+e)/2;
        TreeNode<int> *root = new TreeNode<int>(m[mid]);
  
        root->left = intoBST(m, s, mid-1);
        root->right = intoBST(m, mid+1, e);
  
        return root;
    }
  
    TreeNode<int> *mergeBST(TreeNode<int> *root1, TreeNode<int> *root2){
  
        // convert to inorder vectors
        vector<int> bst1, bst2;
        inorder(root1, bst1);
        inorder(root2, bst2);
  
        // merge vectors
        vector<int> mergedArray = merge(bst1, bst2);
  
        // convert vector to BST
        return intoBST(mergedArray, 0, mergedArray.size()-1);
  
    }
  

Approach 2: Using Doubly Linked List

• Time Complexity :- O(n+m)

• Space Complexity :- O(h1+h2)

• Self-explanatory Code:-

    void convertToDLL(TreeNode<int> *root, TreeNode<int> *&head){
        if(root == NULL){
            return;
        }
  
        convertToDLL(root->right, head);
  
        root->right = head;
  
        if(head!=NULL){
            head->left = root;
        }
  
        head = root;
  
        convertToDLL(root->left, head);
    }
  
    TreeNode<int> *mergedLL(TreeNode<int> *head1, TreeNode<int> *head2){
        TreeNode<int> *head = NULL;
        TreeNode<int> *tail = NULL;
  
        while(head1 != NULL && head2 != NULL){
            if(head1->data < head2->data){
                if(head == NULL){
                    head = head1;
                    tail = head1;
                    head1 = head1->right;
                }
                else{
                    tail->right = head1;
                    head1->left = tail;
                    tail = head1;
                    head1 = head1->right;
                }
            }
  
            else{
                if(head == NULL){
                    head = head2;
                    tail = head2;
                    head2 = head2->right;
                }
                else{
                    tail->right = head2;
                    head2->left = tail;
                    tail = head2;
                    head2 = head2->right;
                }
            }
        }
  
        while(head1!=NULL){
            tail->right = head1;
            head1->left = tail;
            tail = head1;
            head1 = head1->right;
        }
  
        while(head2!=NULL){
            tail->right = head2;
            head2->left = tail;
            tail = head2;
            head2 = head2->right;
        }
  
        return head;
    }
  
    int count(TreeNode<int> *head){
        int cnt = 0;
        TreeNode<int> *temp = head;
  
        while(temp!=NULL){
            cnt++;
            temp= temp->right;
        }
  
        return cnt;
    }
  
    TreeNode<int> *sortedLLtoBST(TreeNode<int> *&head, int n){
        if(n<=0 || head == NULL){
            return NULL;
        }
  
        TreeNode<int> *leftpart = sortedLLtoBST(head, n/2);
        TreeNode<int> *root = head;
        root->left = leftpart;
  
        head = head->right;
  
        root->right = sortedLLtoBST(head, n-n/2-1);
  
        return root;
    }
  
    TreeNode<int> *mergeBST(TreeNode<int> *root1, TreeNode<int> *root2){
  
        // convert to Sorted DLL
  
        TreeNode<int> *head1 = NULL;
        convertToDLL(root1, head1);
        head1 -> left = NULL;
  
        TreeNode<int> *head2 = NULL;
        convertToDLL(root2, head2);
        head2 -> left = NULL;
  
        // Merge Linked List
        TreeNode<int> *head = mergedLL(head1, head2);
  
        // convert sorted LL to BST
        int n = count(head);
        return sortedLLtoBST(head, n);
    }