Introduction

Merging two binary search trees means combining their values into one valid search tree. The simplest practical strategy is to extract both trees in sorted order, merge the two sorted sequences, and build a balanced BST from the merged result. That gives a clean O(n + m) solution when both trees have n and m nodes.

Why Inorder Traversal Helps

An inorder traversal of a BST visits values in sorted order. That means each input tree can be converted into a sorted list with one traversal.

For example, if the trees contain these values:

• tree 1: 1, 3, 5, 7
• tree 2: 2, 4, 6, 8

their inorder traversals already produce the two sorted sequences you need.

Step 1: Traverse Both Trees

A minimal BST node and inorder helper in Python:

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8def inorder(root, values):
9    if root is None:
10        return
11    inorder(root.left, values)
12    values.append(root.value)
13    inorder(root.right, values)

Now each tree can be flattened into a sorted list.

Step 2: Merge the Sorted Lists

Once you have two sorted lists, merge them exactly the way you would merge two sorted arrays in merge sort.

1def merge_sorted(a, b):
2    i = j = 0
3    merged = []
4
5    while i < len(a) and j < len(b):
6        if a[i] <= b[j]:
7            merged.append(a[i])
8            i += 1
9        else:
10            merged.append(b[j])
11            j += 1
12
13    merged.extend(a[i:])
14    merged.extend(b[j:])
15    return merged

This step is linear in the total number of elements.

Step 3: Build a Balanced BST

If you insert the merged values one by one into a new BST, the result can become badly skewed. A better approach is to build a balanced tree from the sorted array by choosing the middle value as the root.

1def build_balanced(sorted_values):
2    if not sorted_values:
3        return None
4
5    mid = len(sorted_values) // 2
6    return Node(
7        sorted_values[mid],
8        build_balanced(sorted_values[:mid]),
9        build_balanced(sorted_values[mid + 1:]),
10    )

That produces a much healthier result for search performance.

Full Example

1def merge_bsts(root1, root2):
2    values1 = []
3    values2 = []
4
5    inorder(root1, values1)
6    inorder(root2, values2)
7
8    merged = merge_sorted(values1, values2)
9    return build_balanced(merged)
10
11
12def print_inorder(root):
13    if root is None:
14        return
15    print_inorder(root.left)
16    print(root.value, end=" ")
17    print_inorder(root.right)
18
19# Tree 1
20root1 = Node(3, Node(1), Node(5))
21
22# Tree 2
23root2 = Node(6, Node(4), Node(8))
24
25merged_root = merge_bsts(root1, root2)
26print_inorder(merged_root)

Output:

1 3 4 5 6 8

Complexity

The runtime is O(n + m) because:

• inorder traversal of both trees is linear
• merging the two sorted lists is linear
• building the balanced BST is linear

The straightforward version uses O(n + m) extra space for the merged arrays.

Alternative Approaches

You can reduce auxiliary storage by traversing both trees with stacks or iterators and streaming the merge, but that implementation is more complex. For interviews and ordinary application code, the array-based approach is usually the clearest correct answer.

Common Pitfalls

A common mistake is inserting merged values into a new BST one by one. That preserves ordering but can produce a badly unbalanced tree.

Another mistake is forgetting that inorder traversal is sorted only because the input is a valid BST. If one tree violates BST rules, the whole merge logic breaks.

A third issue is ignoring duplicates. Decide whether duplicates should be preserved, removed, or counted differently before you finalize the merge logic.

Summary

• Inorder traversal turns each BST into a sorted list
• Merge the two sorted lists in linear time
• Build a balanced BST from the merged sorted values
• The simple solution runs in O(n + m) time with O(n + m) extra space
• Avoid rebuilding the final BST by repeated insertion if you want good balance