☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Merge 2 BST's

Hard TUF ID 2772 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the roots of two binary search trees with m and n nodes. Return a list of all keys from both trees in ascending order. A key that appears in both trees appears twice in the output. Either tree may be empty.

Constraints (LeetCode version): up to 5000 nodes per tree, keys between -10^5 and 10^5. The interesting part is not the size but the follow-up: use the BST ordering instead of a general sort, and keep extra memory proportional to the trees’ heights, not their sizes.

Some versions (for example on GeeksforGeeks) ask you to “merge two BSTs” and return this sorted list; others ask for one balanced BST containing all keys. The sorted list is the hard part of both: a balanced BST is built from it by making the middle element the root and recursing on each half.

Example 1

root1:   2        root2:   1
        / \               / \
       1   4             0   3

answer = [0, 1, 1, 2, 3, 4]      // 1 is in both trees, so it appears twice

Example 2

root1 = [0, -10, 10], root2 = [5, 1, 7, 0, 2]   (level order)
answer = [-10, 0, 0, 1, 2, 5, 7, 10]

Approach 1: Brute force, collect and sort

Intuition. The output is just the multiset of all keys, sorted. Collect every key from both trees into one list and sort it. This treats the trees as bags of numbers and throws away the fact that each one already knows its keys’ order.

Algorithm.

  1. Traverse both trees and append every key to one list.
  2. Sort the list and return it.
static List<Integer> bruteForce(TreeNode root1, TreeNode root2) {
    List<Integer> all = new ArrayList<>();
    collectInorder(root1, all);
    collectInorder(root2, all);
    Collections.sort(all);
    return all;
}

static void collectInorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    collectInorder(node.left, out);
    out.add(node.val);
    collectInorder(node.right, out);
}

Complexity. Time O((m + n) log(m + n)) for the sort. Space O(m + n) for the list.

Approach 2: Better, two in-order lists and a merge

Intuition. In-order traversal of a BST yields its keys already sorted. So we get two sorted lists for linear time, and two sorted lists combine into one with the merge step of merge sort: look at the front of each list, take the smaller, advance that list. Ties can go either way; taking from the first list keeps the result stable.

Algorithm.

  1. In-order traverse root1 into a and root2 into b.
  2. With indices i and j, repeatedly append the smaller of a[i] and b[j] and advance that index.
  3. When one list runs out, append the rest of the other.
static List<Integer> better(TreeNode root1, TreeNode root2) {
    List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
    collectInorder(root1, a);
    collectInorder(root2, b);
    List<Integer> out = new ArrayList<>(a.size() + b.size());
    int i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        if (a.get(i) <= b.get(j)) out.add(a.get(i++));
        else out.add(b.get(j++));
    }
    while (i < a.size()) out.add(a.get(i++));
    while (j < b.size()) out.add(b.get(j++));
    return out;
}

Complexity. Time O(m + n): each key is visited once in the traversal and once in the merge. Space O(m + n) for the two intermediate lists, in addition to the output.

The intermediate lists are the waste. The merge only ever looks at the next key of each tree, so we do not need the whole list in advance, only a way to produce keys one at a time in sorted order.

Approach 3: Optimal, two in-order traversals in lockstep

Intuition. An iterative in-order traversal keeps a stack holding the “left spine” of the part of the tree not yet visited. Its top is always the smallest unvisited key. After popping a node, we push the left spine of its right subtree, and the new top is again the smallest unvisited key. Running two such traversals gives us, at every moment, the next key of each tree, which is exactly what the merge step needs. Pop from whichever stack has the smaller top, emit it, and refill that stack.

Each stack holds at most one root-to-leaf path of its tree, so the extra memory is O(h1 + h2) instead of O(m + n).

Algorithm.

  1. Push the left spine of root1 onto s1 and of root2 onto s2.
  2. While either stack is non-empty: choose s1 if s2 is empty or s1’s top key is <= s2’s top key; otherwise choose s2.
  3. Pop the chosen stack’s top, append its key, and push the left spine of its right child onto the same stack.
static List<Integer> optimal(TreeNode root1, TreeNode root2) {
    Deque<TreeNode> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
    pushLeft(s1, root1);
    pushLeft(s2, root2);
    List<Integer> out = new ArrayList<>();
    while (!s1.isEmpty() || !s2.isEmpty()) {
        Deque<TreeNode> from;
        if (s2.isEmpty() || (!s1.isEmpty() && s1.peek().val <= s2.peek().val)) from = s1;
        else from = s2;
        TreeNode node = from.pop();
        out.add(node.val);
        pushLeft(from, node.right);              // the next key of that tree is the leftmost node of node.right
    }
    return out;
}

static void pushLeft(Deque<TreeNode> stack, TreeNode node) {
    while (node != null) {
        stack.push(node);
        node = node.left;
    }
}

Dry run on Example 1. Initially s1 = [2, 1] and s2 = [1, 0] (bottom to top).

s1 top s2 top take emitted refill
1 0 s2 0 0 has no right child
1 1 s1 (tie) 1 1 has no right child
2 1 s2 1 push spine of 3: s2 = [3]
2 3 s1 2 push spine of 4: s1 = [4]
4 3 s2 3 s2 empty
4 empty s1 4 s1 empty

Result: [0, 1, 1, 2, 3, 4].

Complexity. Time O(m + n): every node is pushed once and popped once across both traversals. Space O(h1 + h2) for the stacks, beyond the output list itself. On balanced trees that is logarithmic; on skewed trees it degrades to linear, which is still no worse than Approach 2.

The same “lazy in-order cursor” is the BST iterator: pushLeft plus “pop, then push the left spine of the right child” is the entire iterator, written inline here for two trees.

Edge cases and pitfalls