Pattern visualizer

Merge Two BSTs

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. 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]..

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 treestep 1 / 15

tree1 | tree2

line 1

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

Where to practice BST

Practice BST problems All BST problems Back to roadmap