Merge Two BSTs

Flatten both trees inorder, merge the sorted lists, rebuild balanced

time O(m + n)space O(m + n) for the flattened arrays and the output tree

Repeatedly inserting one tree's nodes into the other can degrade to O(n^2) on a skewed tree. But an inorder traversal of any BST is already sorted — so flattening both trees gives two sorted arrays, which merge in linear time exactly like the merge step of merge sort. Recursively rooting each slice of the merged array at its middle element then rebuilds a tree that is height-balanced by construction, not just correct.

Details

Animated on: root1 = [2, 1, 4], root2 = [1, 0, 3] — merge every value from both BSTs into a single BST. Expected inorder of the result: [0, 1, 1, 2, 3, 4].

Problem:Merge Two BSTsMedium

Flatten both trees inorder, merge the sorted lists, rebuild balanced

step 1 / 15

tree1 | tree2

tree1 (root 2) and tree2 (root 1) each need every value merged into one BST. Inserting tree2's nodes into tree1 one at a time can go quadratic on a skewed tree, so flatten both to sorted arrays first.

Pseudocode

1FUNCTION mergeTwoBSTs(root1, root2):
2  list1 <- INORDER(root1)
3  list2 <- INORDER(root2)
4  merged <- MERGE(list1, list2)
5  buildBalanced(merged, 0, LENGTH(merged) - 1, null, ROOT)
6  RETURN ROOT
7FUNCTION buildBalanced(arr, left, right, parent, side):
8  IF left > right: RETURN
9  mid <- (left + right) / 2
10  node <- new Node(arr[mid])
11  ATTACH node TO parent AT side
12  buildBalanced(arr, left, mid - 1, node, LEFT)
13  buildBalanced(arr, mid + 1, right, node, RIGHT)

← / → step · space play · Home restart

Every step in words

Show all 15 steps

tree1 (root 2) and tree2 (root 1) each need every value merged into one BST. Inserting tree2's nodes into tree1 one at a time can go quadratic on a skewed tree, so flatten both to sorted arrays first.
Inorder(tree1) visits 1: it is a leaf with no left child, so it is emitted the moment it is reached. Emitted so far: [1].
Inorder(tree1) visits 2: its left subtree is fully emitted, so it is emitted next, before its right subtree. Emitted so far: [1, 2].
Inorder(tree1) visits 4: it is a leaf with no left child, so it is emitted the moment it is reached. Emitted so far: [1, 2, 4].
Inorder(tree2) visits 0: it is a leaf with no left child, so it is emitted the moment it is reached. Emitted so far: [0].
Inorder(tree2) visits 1: its left subtree is fully emitted, so it is emitted next, before its right subtree. Emitted so far: [0, 1].
Inorder(tree2) visits 3: it is a leaf with no left child, so it is emitted the moment it is reached. Emitted so far: [0, 1, 3].
Two-pointer merge combines [1, 2, 4] and [0, 1, 3] into one sorted array: [0, 1, 1, 2, 3, 4]. Each step advances whichever pointer holds the smaller value, so both trees are fully consumed in O(m + n).
build(0, 5): index 2 of the merged array holds 1 — that is the middle of the whole merged array, so 1 becomes the root.
build(0, 1): index 0 of the merged array holds 0 — that is attached as 1's left child.
build(1, 1): index 1 of the merged array holds 1 — that is attached as 0's right child.
build(3, 5): index 4 of the merged array holds 3 — that is attached as 1's right child.
build(3, 3): index 3 of the merged array holds 2 — that is attached as 3's left child.
build(5, 5): index 5 of the merged array holds 4 — that is attached as 3's right child.
Build complete: every recursive call always picks the middle of its own slice, so no path from root to leaf can be more than one level deeper than any other — the tree is height-balanced by construction, and it took one linear pass over the 6-element merged array.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Merge Two BSTs in the editor All BST problems Back to roadmap