All Elements in Two Binary Search Trees - Solution & Explanation

Problem Overview: You are given the roots of two Binary Search Trees. Each BST stores values in sorted order when traversed using in‑order traversal. The task is to return a single sorted list containing every element from both trees.

The key observation: an in-order traversal of a BST already produces a sorted sequence. If you extract the values from both trees in sorted order, the problem becomes identical to merging two sorted arrays.

Approach 1: In-Order Traversal and Merging (Time: O(n + m), Space: O(n + m))

Traverse both trees using in-order traversal from Depth-First Search. Store the result of each traversal in two arrays. Because the trees are BSTs, both arrays are already sorted. Then perform a classic two-pointer merge similar to the merge step of merge sort: compare the current elements from both arrays and append the smaller one to the result. Continue until both arrays are exhausted.

This approach is straightforward and easy to reason about. The traversal step takes O(n) and O(m) for the two trees, and merging takes O(n + m). The tradeoff is memory usage since both arrays store every node value. For most interview scenarios, this solution is perfectly acceptable because of its clarity.

Approach 2: Iterative In-Order Traversal with Stacks (Time: O(n + m), Space: O(h1 + h2))

This method avoids storing the full traversal arrays. Instead, simulate in-order traversal on both trees simultaneously using two stacks. Push left nodes from each tree until you reach the smallest available values. At each step, compare the top nodes of the stacks and pop the smaller one, adding it to the result. After popping a node, move to its right subtree and repeat the left traversal.

This works because each stack always exposes the next smallest element from its tree. Comparing the stack tops effectively mimics the merge step while generating values lazily. The total time remains O(n + m), but extra memory drops to O(h1 + h2), where h1 and h2 are the tree heights.

The algorithm combines concepts from tree traversal and sorted merging. It is especially useful when the trees are large and you want to avoid building full intermediate arrays.

Recommended for interviews: Start with the in-order traversal + merge approach to show you understand BST properties and sorted merging. Then mention the stack-based traversal as an optimization that reduces memory usage while keeping O(n + m) time complexity. Interviewers typically appreciate seeing both approaches and the reasoning behind the tradeoff.