STEP 14 · BINARY SEARCH TREES · DETOUR THROUGH SORTED ARRAYS · MEDIUM

Merge Two Binary Search Trees

WHAT IT SAYS

Combine all elements of two BSTs into one balanced BST (or output their union in sorted order).

WHAT IT'S REALLY ASKING

"A BST and a sorted array are the same information in two shapes — inorder converts one way, middle-as-root converts back, both linear. So don't merge trees; change representation. Two trees become two sorted arrays, two sorted arrays merge with the zipper you already know, and the merged array folds back into a perfectly balanced tree. Every step is a solved problem."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Insert every node of the smaller tree into the larger

O(m·h) insertions — and h grows as you insert, with no balance guarantee

Traverse the second tree; insert each of its m values into the first tree with standard BST insertion.

WHERE THE WORK IS WASTED — Each insertion is an independent O(h) descent from the root, re-walking shared path prefixes m times over — but the deeper failure is what the insertions ignore: the second tree's values arrive with an ORDER (its inorder is sorted), and one-at-a-time insertion discards that order entirely, treating a sorted stream as random arrivals. Punishment follows: feeding sorted values into naive BST insertion is the exact recipe for a spine, so the merged tree can degrade toward a linked list — the output structure is worse than either input, after paying O(m log(n+m)) at best for the privilege.

KEY OBSERVATION — THE UNLOCKlink

A BST and a sorted array are interchangeable.

Three conversions, each linear, each individually familiar — the insight is that chaining them IS the algorithm. First: a BST flattens to a sorted array in O(n) — inorder traversal, the fact underneath the k-th smallest and validation problems. Run it on both trees: two sorted arrays, sizes n and m. Second: two sorted arrays merge in O(n + m) with the two-pointer zipper — compare heads, take the smaller, advance that pointer. This is mergesort's merge step, and notice how it beats insertion philosophically: insertion asks 'where does this value go?' m separate times, paying a search each time; the zipper never searches, because sortedness makes the next output element always one of two known candidates. Order in, order out, no queries. Third: a sorted array folds back into a HEIGHT-BALANCED BST in O(n + m) — take the middle element as root, recurse on each half. Balance is automatic: the two halves differ by at most one element, so the recursion halves the problem evenly at every level and the height is forced to O(log(n+m)). Where naive insertion left balance to luck (and sorted input made luck hostile), the middle-as-root construction makes balance a structural consequence. The composed pipeline: inorder both → zipper merge → middle-as-root rebuild. O(n + m) time end to end, O(n + m) working space. Every stage is a problem you've already solved; the merge problem itself dissolved into representation changes. The general principle deserves stating baldly: when an operation is awkward on a structure, ask whether the structure has a LOSSLESS twin on which the operation is natural. BST ↔ sorted array is the canonical such pair — search-optimised versus scan-and-merge-optimised views of identical information — and round-tripping through the twin is often cheaper than fighting the original shape. (If only a sorted STREAM of the union is needed, skip stage three and even stage one's materialisation: two stack-based inorder iterators zipper directly in O(h1 + h2) space.)

Inorder, zipper, middle-as-root

O(n + m) time, O(n + m) space (O(h1 + h2) for the iterator variant)

Inorder-flatten both trees into arrays A and B. Merge with two pointers into C. Build: mid = middle of range, node = C[mid], left child from the left half, right child from the right half, empty range returns null. For streamed output without full materialisation, drive two explicit-stack inorder iterators and emit the smaller top at each step.

WHAT YOU TRADED — The pipeline pays O(n + m) memory for the array detour — the price of guaranteed balance and linear time — while the iterator variant trades the balanced output for O(h) space when only the sorted union is needed; naive insertion wins only when m is tiny relative to n AND the first tree must be preserved in place. The transferable lesson: hard operations on a structure often become trivial in an equivalent representation — convert, solve, convert back, and let each leg be a problem you already own.

WATCH THE IDEA RUN

BST A

BST B

A's INORDER (already sorted)

B's INORDER (already sorted)

MERGED

—

BST ⇄ sorted array two views, one object

total cost O(m + n)

Inserting every node of B into A one by one works, but it is O(n log n) at best and can degrade to O(n·h) — and it ignores what both inputs already are.

step 1 / 10

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Round-Trip Through the Twin Representation

YOU'LL SEE IT AGAIN WHEN

The structure has a lossless linear twin (BST ↔ sorted array, heap ↔ array, tree ↔ traversal-with-nulls) and the operation is natural on the twin.
The operation combines two instances — merging, intersecting, unioning — which linear representations handle with zippers instead of repeated searches.
Rebuilding from the twin gives structural guarantees (balance) that incremental modification cannot promise.

SAME BLUEPRINT, DIFFERENT PROBLEM

Convert Sorted Array to Binary Search TreeMerge Two Sorted ListsAll Elements in Two Binary Search TreesBalance a Binary Search Tree (the same round-trip, one tree)

The bar isn't "solved it once." It's "could rebuild it from the observation."