Solution

The correct answer is: Option 2) O(m + n)

Key Points

Given: Two balanced Binary Search Trees (BSTs), one with m nodes and the other with n nodes.

Objective: Merge them into a new balanced Binary Search Tree.

Approach:

1. Step 1: Perform in-order traversal of both BSTs.
   This will give two sorted arrays of size m and n, respectively.
   Time complexity for in-order traversal of both trees = O(m + n)
2. Step 2: Merge the two sorted arrays.
   This is similar to merging in merge sort.
   Time complexity = O(m + n)
3. Step 3: Construct a balanced BST from the merged sorted array.
   This can be done using a divide-and-conquer approach (similar to building BST from sorted array).
   Time complexity = O(m + n)

Total Time Complexity: O(m + n) + O(m + n) + O(m + n) = O(m + n)

Conclusion:
Merging two balanced BSTs into one balanced BST can be done in linear time with respect to the total number of nodes.

✅ Final Answer: Option 2) O(m + n)