Merge Two BSTs

Merge Two BSTs asks you to combine two binary search trees into one balanced BST. The clean trick is to stop thinking about trees and start thinking about sorted lists — a BST and a sorted array are two views of the same ordered data.

The slow way first

The naive approach: insert every node of the second tree into the first, one at a time. Each insert is O(h), and if the tree degenerates into a chain, h is O(n) — so inserting n nodes is O(n²), and the result is not even guaranteed to be balanced.

The question to ask: what structure makes both trees easy to combine? A BST traversed inorder comes out already sorted. Two sorted lists are trivial to merge, and a sorted list rebuilds into a balanced BST for free.

The idea: trees → sorted lists → balanced tree

Three moves. First, inorder-traverse each BST to get two sorted arrays. Second, merge the two sorted arrays the merge-sort way (compare fronts, take the smaller). Third, build a balanced BST from the merged array by picking the middle element as the root and recursing on each half.

The key insight: picking the middle of a sorted array as the root splits it into two equal halves, so the tree it builds is height-balanced by construction.

Walk through it

Step through the animation. First each tree flattens to its sorted inorder list. Then the two lists merge into [1, 3, 5, 7, 8, 9]. Finally the middle element 5 becomes the root, the left half [1, 3] builds the left subtree, and the right half [7, 8, 9] builds the right — a balanced BST.

Pseudocode

inorder(tree)  -> sorted list of its values     # left, node, right
a = inorder(tree1)
b = inorder(tree2)
merged = merge two sorted lists a and b
build_balanced(arr, lo, hi):
    if lo > hi: return None                      # empty range
    mid = (lo + hi) // 2                          # middle is the root
    node = arr[mid]
    node.left  = build_balanced(arr, lo, mid - 1) # left half
    node.right = build_balanced(arr, mid + 1, hi) # right half
    return node
return build_balanced(merged, 0, len(merged) - 1)

The Python solution

def merge_bsts(root1, root2):
    def inorder(node, out):
        if node:
            inorder(node.left, out)
            out.append(node.val)
            inorder(node.right, out)
    a, b = [], []
    inorder(root1, a)
    inorder(root2, b)
    merged = merge_sorted(a, b)
    return build_balanced(merged, 0, len(merged) - 1)
 
def build_balanced(arr, lo, hi):
    if lo > hi:
        return None
    mid = (lo + hi) // 2
    node = TreeNode(arr[mid])
    node.left = build_balanced(arr, lo, mid - 1)
    node.right = build_balanced(arr, mid + 1, hi)
    return node

• inorder walks a BST left-root-right, appending values, so a and b come out already sorted.
• merge_sorted(a, b) merges two sorted lists in one pass by repeatedly taking the smaller front — the same merge step as merge sort.
• build_balanced picks mid as the root (line 16) so each side gets an equal share of the array.
• The two recursive calls (lines 18 and 19) build the left and right subtrees from the two halves.
• The base case lo > hi returns None for an empty range, which stops the recursion.

Complexity

Everything is linear in the total number of nodes. We use O(m + n) extra space for the two lists and the recursion stack — a clean trade for a guaranteed-balanced result.

When this pattern shows up

Practice