All Elements in Two Binary Search Trees: Inorder Merge

Given two binary search trees root1 and root2, return a list containing all the integers from both trees, sorted in ascending order.

This is LeetCode 1305: All Elements in Two Binary Search Trees. It combines two fundamental techniques you should already know: inorder traversal of a BST and the merge step from merge sort. If you can do both, this problem clicks immediately.

Example: root1 = [2, 1, 4], root2 = [1, 0, 3]. The answer is [0, 1, 1, 2, 3, 4].

Why this problem matters

This problem is a clean test of whether you truly understand the BST property. A lot of people know that "BSTs are sorted," but knowing it and using it are different things. Here you need to turn that property into an algorithm: extract sorted order from each tree, then combine the results.

It also reinforces a pattern you will use again and again. Any time you have two sorted sequences and need to combine them, the two-pointer merge is the tool. You see it in merge sort, in merging sorted linked lists, and here with BSTs. Drilling this problem locks in both the traversal and the merge as building blocks you can reach for automatically.

The key insight

An inorder traversal of a BST visits nodes in sorted order. That is not a coincidence; it follows directly from the BST definition. Every node in the left subtree is smaller than the root, and every node in the right subtree is larger. Visiting left, then root, then right naturally produces ascending order.

So the plan is:

1. Run inorder traversal on root1 to get a sorted list.
2. Run inorder traversal on root2 to get another sorted list.
3. Merge the two sorted lists into one, just like the merge step in merge sort.

The merge uses two pointers, one for each list. At each step, compare the current elements and pick the smaller one. When one list runs out, append the rest of the other. The result is a single sorted list containing every element from both trees.

The solution

def get_all_elements(root1, root2):
    def inorder(node, result):
        if not node:
            return
        inorder(node.left, result)
        result.append(node.val)
        inorder(node.right, result)

    list1, list2 = [], []
    inorder(root1, list1)
    inorder(root2, list2)

    merged = []
    i = j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            merged.append(list1[i])
            i += 1
        else:
            merged.append(list2[j])
            j += 1
    merged.extend(list1[i:])
    merged.extend(list2[j:])
    return merged

The inorder helper does a standard recursive traversal. It appends values in left-root-right order, which gives sorted output for any BST. After collecting both sorted lists, the while loop does a classic two-pointer merge: compare list1[i] and list2[j], take the smaller one, advance that pointer. Once one list is exhausted, extend adds whatever remains from the other.

The condition list1[i] <= list2[j] (using <=) ensures stability: when both values are equal, we take from list1 first. This does not affect correctness since both produce valid sorted output, but it keeps the merge deterministic.

Visual walkthrough

Let's trace through the example step by step. Tree 1 has nodes [2, 1, 4] and Tree 2 has nodes [1, 0, 3].

The first step leverages the BST property to get sorted lists without any explicit sorting. The second step uses the merge pattern to combine them in linear time. Together, they solve the problem optimally.

Complexity analysis

Here m is the number of nodes in root1 and n is the number in root2. You cannot do better than O(m + n) time because every element must appear in the output. The space is also O(m + n) because the output itself has that many elements.

The building blocks

Inorder traversal of a BST

The recursive pattern inorder(left) -> visit -> inorder(right) is one of the most reusable building blocks in tree problems. For a BST, it gives you sorted order for free. You will use it in Validate BST (LeetCode 98), Kth Smallest Element in a BST (LeetCode 230), and many others. If you can write this three-line helper from memory, you already have the core of this solution.

Merging two sorted arrays

The two-pointer merge is the heart of merge sort and appears in many problems beyond sorting. You keep two indices, compare the current elements, take the smaller one, and advance. When one input runs out, you extend with the remainder. This same logic applies to merging sorted linked lists (LeetCode 21), merging k sorted lists with a heap (LeetCode 23), and finding intersections of sorted arrays.

Edge cases

• One or both trees are empty: if root1 is None, the inorder traversal returns an empty list. The merge loop never executes for that side, and extend adds all of list2. The code handles this without special cases.
• Trees of very different sizes: the merge still runs in O(m + n). The smaller list gets exhausted first, and the remaining elements from the larger list are appended in one extend call.
• Duplicate values across trees: the <= comparison in the merge handles duplicates naturally. Equal values from both trees end up adjacent in the output, which is correct.
• Single-node trees: each inorder traversal returns a one-element list. The merge compares the two values and produces a two-element sorted output.

From understanding to recall

You now see how this problem breaks into two independent building blocks: inorder traversal and two-pointer merge. Each one is simple on its own. The insight is recognizing that the BST property hands you sorted input for free, turning the problem into a merge of two sorted lists.

But recognizing this during an interview requires having practiced both building blocks individually. If you have drilled inorder traversal and the merge pattern separately, combining them here feels natural. If you have not, you might waste time considering more complicated approaches like inserting all nodes into a heap or doing a single combined traversal.

Spaced repetition helps you internalize each building block so you can assemble them on the fly. You type the inorder helper from memory one day, the merge loop another day, and eventually the full solution comes together without hesitation.

Related posts

• Binary Tree Inorder Traversal - The foundational traversal pattern used in the first step of this solution
• Merge Sorted Array - The same two-pointer merge technique, applied in-place with the backwards trick
• Validate Binary Search Tree - Another problem that relies on the BST inorder property to verify sorted order

Understanding these building blocks individually makes combining them feel automatic. That is the difference between solving problems from scratch and assembling solutions from pieces you already know.