Problem Description

You are given two binary search trees, root1 and root2. Your task is to combine all the integers from both trees and return them in a single list sorted in ascending order.

The problem requires you to:

1. Extract all values from the first binary search tree
2. Extract all values from the second binary search tree
3. Combine all these values together
4. Return them as a sorted list in ascending order

Since both inputs are binary search trees (BSTs), their in-order traversal naturally gives values in sorted order. The solution leverages this property by:

• Performing an in-order traversal (left → root → right) on each tree to get two sorted arrays a and b
• Merging these two sorted arrays using a two-pointer technique to produce the final sorted result

The merging process compares elements from both arrays and adds the smaller one to the result, similar to the merge step in merge sort. After one array is exhausted, any remaining elements from the other array are appended to complete the merged list.

For example, if root1 contains values [1, 4, 6] and root2 contains values [2, 3, 5], the final output would be [1, 2, 3, 4, 5, 6].

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: Binary search trees are a special type of graph structure where each node has at most two children (left and right), forming a hierarchical tree structure.

Is it a tree?

• Yes: The problem explicitly states we're working with two binary search trees. Trees are connected acyclic graphs with a root node and parent-child relationships.

DFS

• Conclusion reached: Since we're dealing with trees, the flowchart leads us directly to DFS (Depth-First Search).

The flowchart confirms that DFS is the appropriate pattern for this problem. This makes sense because:

1. We need to visit every node in both trees to collect all values
2. In-order traversal (a type of DFS) on a BST naturally gives us sorted values
3. DFS allows us to recursively traverse the tree structure efficiently, visiting left subtree, then root, then right subtree

The solution implements DFS through the recursive dfs function that performs in-order traversal on each tree, collecting values in sorted order. This leverages the BST property where in-order traversal yields sorted sequences, which can then be merged efficiently.

Intuition

When we need to combine elements from two binary search trees into a single sorted list, the key insight is recognizing that BSTs have a special property: an in-order traversal naturally produces values in sorted order.

Think about how in-order traversal works: we visit the left subtree first (which contains smaller values), then the current node, then the right subtree (which contains larger values). This left-root-right pattern guarantees that we process nodes in ascending order.

Since we have two BSTs, we can:

1. Extract a sorted list from the first tree using in-order traversal
2. Extract a sorted list from the second tree using in-order traversal
3. Now we have two sorted arrays - this transforms our tree problem into a simpler array problem

At this point, we need to combine two sorted arrays into one. This is a classic merge operation, similar to what's done in merge sort. We use two pointers, one for each array, and at each step we compare the current elements and take the smaller one. This ensures our final result maintains sorted order.

Why is this approach efficient? Instead of collecting all values unsorted and then sorting them (which would take O(n log n) time), we leverage the BST structure to get already-sorted sequences through DFS traversal in O(n) time. The merge step is also O(n), making our overall solution linear in the total number of nodes.

The beauty of this solution lies in decomposing the problem: first use the tree structure to our advantage (getting sorted sequences via DFS), then solve a simpler problem (merging sorted arrays).

Learn more about Tree, Depth-First Search, Binary Search Tree, Binary Tree and Sorting patterns.

Solution Approach

The solution implements the DFS + Merge approach in two main phases:

Phase 1: Extract sorted values using DFS

The dfs helper function performs an in-order traversal on each tree:

def dfs(root: Optional[TreeNode], nums: List[int]) -> int:
    if root is None:
        return
    dfs(root.left, nums)    # Visit left subtree first
    nums.append(root.val)    # Process current node
    dfs(root.right, nums)    # Visit right subtree last

This recursive function follows the left-root-right pattern. For a BST, this guarantees values are collected in ascending order. We call this function twice:

• dfs(root1, a) populates array a with sorted values from the first tree
• dfs(root2, b) populates array b with sorted values from the second tree

Phase 2: Merge two sorted arrays

With two sorted arrays a and b, we use the two-pointer technique to merge them:

i = j = 0
ans = []
while i < m and j < n:
    if a[i] <= b[j]:
        ans.append(a[i])
        i += 1
    else:
        ans.append(b[j])
        j += 1

The algorithm maintains pointers i and j for arrays a and b respectively. At each step:

• Compare a[i] with b[j]
• Append the smaller value to the result
• Advance the pointer of the array from which we took the element

After one array is exhausted, we append any remaining elements:

while i < m:
    ans.append(a[i])
    i += 1
while j < n:
    ans.append(b[j])
    j += 1

Time Complexity: O(m + n) where m and n are the number of nodes in each tree. We visit each node once during traversal and process each element once during merging.

Space Complexity: O(m + n) for storing the values in arrays a, b, and the final result ans.

Example Walkthrough

Let's walk through a concrete example to see how the solution works step by step.

Given Trees:

Tree 1:        Tree 2:
    2              1
   / \            / \
  1   4          0   3

Phase 1: Extract sorted values using DFS (in-order traversal)

For Tree 1 (root1):

• Start at root (2)
• Go left to node (1)
  • Node 1 has no left child
  • Add 1 to array: a = [1]
  • Node 1 has no right child
• Back at root (2), add 2: a = [1, 2]
• Go right to node (4)
  • Node 4 has no left child
  • Add 4 to array: a = [1, 2, 4]
  • Node 4 has no right child
• Result: a = [1, 2, 4]

For Tree 2 (root2):

• Start at root (1)
• Go left to node (0)
  • Node 0 has no left child
  • Add 0 to array: b = [0]
  • Node 0 has no right child
• Back at root (1), add 1: b = [0, 1]
• Go right to node (3)
  • Node 3 has no left child
  • Add 3 to array: b = [0, 1, 3]
  • Node 3 has no right child
• Result: b = [0, 1, 3]

Phase 2: Merge two sorted arrays

Now merge a = [1, 2, 4] and b = [0, 1, 3]:

Now j = 3 equals length of b, so the first while loop exits. Append remaining elements from a: Add a[2]=4

Final Result: [0, 1, 1, 2, 3, 4]

The algorithm efficiently combines both trees by leveraging the BST property to get sorted sequences through DFS, then merging them in linear time.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm consists of three main phases:

1. In-order traversal of the first tree: The dfs function visits each node in root1 exactly once, taking O(n) time where n is the number of nodes in the first tree.
2. In-order traversal of the second tree: Similarly, the dfs function visits each node in root2 exactly once, taking O(m) time where m is the number of nodes in the second tree.
3. Merging two sorted arrays: The while loops iterate through arrays a and b exactly once. Each element from both arrays is processed exactly once, taking O(n + m) time.

Therefore, the total time complexity is O(n) + O(m) + O(n + m) = O(n + m).

Space Complexity: O(n + m)

The space usage includes:

1. Array a: Stores all n values from the first tree, using O(n) space.
2. Array b: Stores all m values from the second tree, using O(m) space.
3. Result array ans: Stores all n + m elements from both trees, using O(n + m) space.
4. Recursion call stack: The in-order traversal uses recursion with maximum depth equal to the height of each tree. In the worst case (skewed tree), this could be O(n) for the first tree and O(m) for the second tree. However, this doesn't add to the overall complexity since it's dominated by the array storage.

The dominant space usage comes from storing all elements, resulting in a space complexity of O(n + m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Empty Trees

A common mistake is not properly handling cases where one or both trees are empty. While the provided solution handles this correctly through the base case if root is None: return, developers often forget to test edge cases like:

• Both trees are empty (should return [])
• Only one tree is empty (should return all elements from the non-empty tree)

Solution: Always include null checks in your traversal function and test with empty tree inputs.

2. Using Wrong Tree Traversal Order

Since we need sorted output and are working with BSTs, using pre-order or post-order traversal instead of in-order traversal would give incorrectly ordered results.

Incorrect approach:

def preorder_traversal(root, elements):
    if root is None:
        return
    elements.append(root.val)  # Wrong: Processing node before left subtree
    preorder_traversal(root.left, elements)
    preorder_traversal(root.right, elements)

Solution: Always use in-order traversal (left → root → right) for BSTs to get sorted order.

3. Inefficient Merging by Sorting Combined Arrays

Some developers might combine both arrays and then sort the result:

# Inefficient approach - O((m+n)log(m+n)) time
all_elements = first_tree_elements + second_tree_elements
return sorted(all_elements)

This approach has O((m+n)log(m+n)) time complexity instead of the optimal O(m+n).

Solution: Leverage the fact that both arrays are already sorted and use the two-pointer merge technique for O(m+n) complexity.

4. Modifying Input Lists During Traversal

Passing the same list reference across multiple function calls without clearing it can lead to accumulating values from previous test cases:

# Bug-prone if reusing the same list
elements = []  # Defined outside function
def getAllElements(self, root1, root2):
    inorder_traversal(root1, elements)  # elements might contain old values
    inorder_traversal(root2, elements)

Solution: Always create fresh lists for each function call as shown in the correct implementation.

5. Off-by-One Errors in Merge Logic

Using incorrect comparison operators or loop conditions can cause missing elements or index out of bounds errors:

# Common mistakes:
while pointer_first <= len_first:  # Should be < not <=
    merged_result.append(first_tree_elements[pointer_first])  # IndexError!

Solution: Use strict less-than (<) when comparing indices with list length, and carefully verify loop boundaries.