Merge two BST ‘s

Given two BSTs, return elements of merged BSTs in sorted form.

Examples :

Input:
BST1:
       5
     /   \
    3     6
   / \
  2   4  
BST2:
        2
      /   \
     1     3
            \
             7
            /
           6
Output: 1 2 2 3 3 4 5 6 6 7
Explanation: After merging and sorting the two BST we get 1 2 2 3 3 4 5 6 6 7.

Input:
BST1:
       12
     /   
    9
   / \    
  6   11
BST2:
      8
    /  \
   5    10
  /
 2
Output: 2 5 6 8 9 10 11 12
Explanation: After merging and sorting the two BST we get 2 5 6 8 9 10 11 12.

Expected Time Complexity: O(m+n)
Expected Auxiliary Space: O(Height of BST1 + Height of BST2 + m + n)

Constraints:
1 ≤ Number of Nodes ≤ 10⁵

Approach 01

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> merge(Node* root1, Node* root2) {
        std::vector<int> bstValues1, bstValues2;
        inorderTraversal(root1, bstValues1);
        inorderTraversal(root2, bstValues2);
        
        std::vector<int> mergedValues = bstValues1;
        mergedValues.insert(mergedValues.end(), bstValues2.begin(), bstValues2.end());
        std::sort(mergedValues.begin(), mergedValues.end());
        
        return mergedValues;
    }

private:
    void inorderTraversal(Node* node, std::vector<int>& values) {
        if (node == nullptr) {
            return;
        }
        inorderTraversal(node->left, values);
        values.push_back(node->data);
        inorderTraversal(node->right, values);
    }
};

class Solution:
    def merge(self, root1, root2):
        def inorderTraversal(node, values):
            if not node:
                return
            inorderTraversal(node.left, values)
            values.append(node.data)
            inorderTraversal(node.right, values)
            
        bstValues1, bstValues2 = [], []
        inorderTraversal(root1, bstValues1)
        inorderTraversal(root2, bstValues2)
        
        return sorted(bstValues1 + bstValues2)

Time Complexity

• Inorder Traversal:

  Performing an inorder traversal on each binary search tree (BST) takes \( O(n1) \) time for the first tree and \( O(n2) \) time for the second tree, where \( n1 \) and \( n2 \) are the number of nodes in the respective trees.

• Merging Vectors:

  Inserting the elements of bstValues2 into mergedValues takes \( O(n2) \) time.

• Sorting:

  Sorting the merged vector mergedValues takes \( O((n1 + n2) \log(n1 + n2)\) time, where \( n1 + n2 \) is the total number of elements.

• Overall Time Complexity:

  The overall time complexity is \( O(n1 + n2 + (n1 + n2) \log(n1 + n2)) \), which simplifies to \( O((n1 + n2) \log(n1 + n2)) \).

Space Complexity

• Auxiliary Space:

  Storing the values from the inorder traversal of both BSTs in bstValues1 and bstValues2 takes \( O(n1 + n2) \) space.

• Merged Vector:

  The merged vector mergedValues stores all elements from both trees, resulting in \( O(n1 + n2) \) space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(n1 + n2) \), accounting for the space used by the vectors bstValues1, bstValues2, and mergedValues.