AlgoViz
HomeBinary Search Trees

Merge 2 BST's

Hard

Two in-order traversals, then merge

Problem

Given two BSTs, return a sorted list of all their elements merged together.

In simple words

In-order traverse both BSTs to get two sorted lists, then merge them into one sorted sequence.

The idea

In-order traversal turns each BST into a sorted list, and merging two sorted lists is linear. Using iterative traversals with explicit stacks lets you merge on the fly without materialising both lists.

The trick

  • In-order gives sorted output — that is the whole reason this works.
  • O(m + n) time; the stacks cost O(height) if you merge lazily.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
1
3
2
5
4
6
0
1
2
3
4
5
6
7

Step 1 of 2. Here's the example — BST1 {2,1,3}, BST2 {5,4,6} Values: 1, 2, 1, 3, 2, 5, 4, 6.

1/2
Optimal
timeO(n+m)spaceO(n+m)
1a = inorder(root1); b = inorder(root2)2return merge(a, b)   // like merge sort's merge

Input

array
[1, 2, 1, 3, 2, 5, 4, 6]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
bst1 = [3,1,5], bst2 = [4,2,6]
Output:
[1, 2, 3, 4, 5, 6]
Explanation:
In-order both, then merge the sorted lists.

Example 2

Input:
bst1 = [1], bst2 = [2]
Output:
[1, 2]
Explanation:
1,2.

Example 3

Input:
bst1 = [5,3], bst2 = [4]
Output:
[3, 4, 5]
Explanation:
3,4,5.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.