Merge Two BSTs Into a Sorted List

Given two binary search trees with m and n nodes, return all their values in non-decreasing order, in O(m + n) time.

LeetCode: 1305. All Elements in Two Binary Search Trees

Example

Text

    3          4
   / \        / \
  2   5      1   6

Output: [1, 2, 3, 4, 5, 6]

Brute force: collect and sort

A tree node is an object with an int val and two reference fields, left and right. A missing child is null, and the empty tree is a null root. The fields are mutable, so no wrapper type is needed. The code collects every value into an ArrayList and sorts it with Collections.sort.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

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

    static List<Integer> mergeBsts(TreeNode a, TreeNode b) {
        List<Integer> values = new ArrayList<>();
        collect(a, values);
        collect(b, values);
        Collections.sort(values);
        return values;
    }

    public static void main(String[] args) {
        TreeNode a = fromValues(3, 2, 5);
        TreeNode b = fromValues(4, 1, 6);
        System.out.println(mergeBsts(a, b));
    }
}

Output

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

Time: O((m + n) log(m + n)). Space: O(m + n). It does not use the ordering the trees already have.

Optimal: two in-order iterators, merged

An in-order traversal of a BST yields its values in sorted order. Run one traversal per tree, step by step, and merge them like two sorted arrays: always take the smaller of the two next values.

A recursive in-order cannot be paused between values, so each traversal uses an explicit stack: push a node and all its left descendants; to get the next value, pop a node, then push its right child and that child's left descendants. ArrayDeque used with push, pop, and peek is the standard stack in Java. peek returns null when the stack is empty, which is how the code detects an exhausted tree.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

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

    static List<Integer> mergeBsts(TreeNode a, TreeNode b) {
        Deque<TreeNode> sa = new ArrayDeque<>();
        Deque<TreeNode> sb = new ArrayDeque<>();
        pushLeft(a, sa);
        pushLeft(b, sb);
        List<Integer> result = new ArrayList<>();
        while (!sa.isEmpty() || !sb.isEmpty()) {
            boolean takeA;
            if (sa.isEmpty()) takeA = false;
            else if (sb.isEmpty()) takeA = true;
            else takeA = sa.peek().val <= sb.peek().val;
            Deque<TreeNode> stack = takeA ? sa : sb;
            TreeNode n = stack.pop();
            result.add(n.val);
            pushLeft(n.right, stack);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode a = fromValues(3, 2, 5);
        TreeNode b = fromValues(4, 1, 6);
        System.out.println(mergeBsts(a, b));
        System.out.println(mergeBsts(fromValues(0, -10, 10), fromValues(5, 1, 7, 0, 2)));
        System.out.println(mergeBsts(null, fromValues(2, 1)));
    }
}

Output

[1, 2, 3, 4, 5, 6]
[-10, 0, 0, 1, 2, 5, 7, 10]
[1, 2]

Time: O(m + n). Space: O(h₁ + h₂) for the two stacks, besides the output.

Collecting each tree's in-order values into a list and merging the two lists is also O(m + n) time, but uses O(m + n) extra space.

Edge cases

One tree empty: the other tree's in-order values.
Duplicates across trees: both copies appear, as in 0, 0 above.