You are given the roots of two Binary Search Trees (BSTs):

root1, root2

Your task:

Return a sorted list containing all elements from both trees.

Example:

Input:
root1 = [2,1,4]
root2 = [1,0,3]

Output: [0,1,1,2,3,4]

Another example:

Input:
root1 = []
root2 = [5,4,7]

Output: [4,5,7]

---

Problem Understanding

Important characteristics:

• Both trees are BSTs
• BST property: In-order traversal returns sorted elements
• We must combine values from both trees
• Final output must be globally sorted
• Trees may have different sizes
• Trees may contain overlapping values

So the challenge reduces to:

Extract sorted lists from both BSTs, then merge them.

This is identical to merging two sorted arrays.

---

Logic Explained in Simple English

The simplest way to think about solving this:

1. Perform in-order traversal on the first tree to collect elements in sorted order.
2. Perform in-order traversal on the second tree to collect elements in sorted order.
3. Now you have: list1 sorted list2 sorted
4. Merge them like in merge step of merge sort:
   • Compare front elements
   • Append smaller one
   • Move pointer forward
   • Continue until both lists are consumed

Why this works:

• In-order traversal guarantees sorted output for BST
• Merging two sorted lists takes linear time
• Overall efficiency is optimal

Alternative thought:

You could push both into one list and sort — but that’s unnecessarily slower.

---

Step-by-Step Approach

1. Initialize two empty lists: list1 and list2
2. In-order traverse root1, store into list1
3. In-order traverse root2, store into list2
4. Merge list1 and list2 into result list
5. Return result

Edge cases handled naturally:

• If one tree is empty → result is the other list
• If both empty → return empty list

---

Java Implementation

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        
        inorder(root1, list1);
        inorder(root2, list2);
        
        return merge(list1, list2);
    }
    
    private void inorder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
    
    private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0;
        
        while (i < list1.size() && j < list2.size()) {
            if (list1.get(i) <= list2.get(j)) {
                result.add(list1.get(i++));
            } else {
                result.add(list2.get(j++));
            }
        }
        
        while (i < list1.size()) {
            result.add(list1.get(i++));
        }
        
        while (j < list2.size()) {
            result.add(list2.get(j++));
        }
        
        return result;
    }
}

---

Dry Run Example

Input:

root1 = [2,1,4]
root2 = [1,0,3]

Step 1 — In-order traversal results:

Tree 1:

[1,2,4]

Tree 2:

[0,1,3]

Step 2 — Merge them:

Compare:

0 < 1 → result = [0]
1 ≤ 1 → result = [0,1]
1 < 2 → result = [0,1,1]
2 < 3 → result = [0,1,1,2]
3 < 4 → result = [0,1,1,2,3]
Append remaining 4 → result = [0,1,1,2,3,4]

Final output:

[0,1,1,2,3,4]

---

Time and Space Complexity

Time Complexity

O(m + n)

Where:

• m = number of nodes in root1
• n = number of nodes in root2

Reason:

• Traversing both trees costs O(m+n)
• Merging lists costs O(m+n)

Space Complexity

O(m + n)

To store both traversal lists and result.

---

Common Mistakes and How to Avoid Them

Mistake 1: Sorting after combining lists

This leads to:

O((m+n) log (m+n)) — slower than needed

Mistake 2: Not using BST property

In-order traversal MUST be used.

Mistake 3: Using recursion without null checks

Always check root for null.

Mistake 4: Merging incorrectly by skipping equality case

Use <= to preserve ordering stability.

Mistake 5: Trying to modify trees

No need — collect values only.