Merge two BST

The problem, simply

You get two binary search trees (BSTs), one with m numbers and one with n numbers. Give back all m + n numbers in sorted order. A common second step is to build one balanced BST out of that sorted line.

The interview point is to do it without sorting from scratch, and with extra room only as tall as the two trees (not as big as them), apart from the answer itself.

A story to remember it

Picture it

Examples

Way 1: the simple way

Pour both trees into one list and sort it.

1. Visit every spot in both trees and add its number to a list.
2. Sort the list.
3. If a tree is wanted, build a balanced BST: the middle number on top, the left half on the left, the right half on the right.

import java.util.*;

class Solution {
    public List<Integer> merge(TreeNode a, TreeNode b) {
        List<Integer> all = new ArrayList<>();
        collect(a, all);
        collect(b, all);
        Collections.sort(all);              // sort from scratch
        return all;
    }

    private void collect(TreeNode node, List<Integer> all) {
        if (node == null) return;
        all.add(node.val);
        collect(node.left, all);
        collect(node.right, all);
    }

    public TreeNode toBalancedBST(List<Integer> sorted, int lo, int hi) {
        if (lo > hi) return null;
        int mid = (lo + hi) / 2;
        TreeNode node = new TreeNode(sorted.get(mid));
        node.left = toBalancedBST(sorted, lo, mid - 1);
        node.right = toBalancedBST(sorted, mid + 1, hi);
        return node;
    }
}

How long it takes: sorting m + n numbers, O((m+n) log(m+n)). Extra room: the full list, O(m+n). It wastes the fact that each tree is already sorted.

Way 2: the clever way

Read both trees in sorted order at the same time, and merge as you go, like merging two sorted lines.

Each tree gets a pile (a stack) that holds the road down its left edge. The top of the pile is always that tree's next smallest number.

1. For each tree, push the whole left road from its top: the top, its left child, that one's left child, and so on.
2. Compare the tops of the two piles. Pop the smaller one and add it to the answer.
3. If the popped spot has a right child, push the left road starting from that right child.
4. Repeat until both piles are empty.

import java.util.*;

class Solution {
    public List<Integer> merge(TreeNode a, TreeNode b) {
        Deque<TreeNode> pa = new ArrayDeque<>(), pb = new ArrayDeque<>();
        pushLeft(a, pa);
        pushLeft(b, pb);
        List<Integer> out = new ArrayList<>();
        while (!pa.isEmpty() || !pb.isEmpty()) {
            Deque<TreeNode> from;
            if (pb.isEmpty()) from = pa;
            else if (pa.isEmpty()) from = pb;
            else from = pa.peek().val <= pb.peek().val ? pa : pb;  // the smaller front
            TreeNode node = from.pop();
            out.add(node.val);
            pushLeft(node.right, from);    // the next smallest of that tree
        }
        return out;
    }

    // push the road down the left edge
    private void pushLeft(TreeNode node, Deque<TreeNode> pile) {
        while (node != null) {
            pile.push(node);
            node = node.left;
        }
    }
}

How long it takes: every spot is pushed once and popped once, O(m+n). Extra room besides the answer: the two piles, each only as tall as its tree, O(h1+h2). To finish with a balanced BST, feed out to toBalancedBST from Way 1, which is O(m+n) more.

Another way: rewire the spots, no new nodes

If the task wants one balanced BST made of the original spots, with no copies: turn each tree into a sorted chain in place (reuse right as "next"), merge the two chains like linked lists, then build the tree from the chain by building the left half first while a finger walks the chain. All three steps are O(m+n) and need only recursion room.

class Solution {
    private TreeNode finger;

    public TreeNode mergeToBST(TreeNode a, TreeNode b) {
        TreeNode merged = mergeChains(toChain(a, null), toChain(b, null));
        int n = 0;
        for (TreeNode t = merged; t != null; t = t.right) n++;
        finger = merged;
        return build(n);
    }

    // flatten a tree into a sorted chain along right; tail is what comes after it
    private TreeNode toChain(TreeNode node, TreeNode tail) {
        if (node == null) return tail;
        node.right = toChain(node.right, tail);
        TreeNode head = toChain(node.left, node);
        node.left = null;
        return head;
    }

    private TreeNode mergeChains(TreeNode x, TreeNode y) {
        TreeNode dummy = new TreeNode(0), t = dummy;
        while (x != null && y != null) {
            if (x.val <= y.val) { t.right = x; x = x.right; }
            else { t.right = y; y = y.right; }
            t = t.right;
        }
        t.right = (x != null) ? x : y;
        return dummy.right;
    }

    // build a balanced tree from the next n spots of the chain
    private TreeNode build(int n) {
        if (n <= 0) return null;
        TreeNode left = build(n / 2);
        TreeNode root = finger;
        finger = finger.right;
        root.left = left;
        root.right = build(n - n / 2 - 1);
        return root;
    }
}

Watch out for

• When one pile runs out, keep taking from the other. Do not stop the loop early.
• After popping a spot, push the left road of its right child, not just the right child itself.
• Repeated numbers across trees. Decide whether to keep both. For a BST with no repeats, skip a number equal to the last one added.

What interviewers ask next

• Find pairs, one from each tree, that add up to x. Walk A from smallest up and B from biggest down with two piles, like two pointers. See "Count pairs from 2 BST whose sum is equal to given value X".
• Merge k BSTs. Keep one pile per tree and a small heap of their fronts. O(N log k) for N total numbers.
• Check if two BSTs hold the same numbers. Walk both in order at the same time and compare, stopping at the first difference.
• Why O(h1+h2) and not O(1)? The piles remember how to climb back up. A Morris walk can make it O(1) but it changes the trees while it runs.

Remember this

Grown-up words: the two lunch lines are two inorder traversals, the pile of the left road is an iterative inorder stack, taking the smaller front is the merge step of merge sort, and "the middle on top" builds a height-balanced BST.