All Elements in Two Binary Search Trees

medium bst merge

Problem

Given two binary search trees root1 and root2, return a list of all the integers in both trees in ascending order.

Inputroot1 = [2,1,4], root2 = [1,0,3]

Output[0, 1, 1, 2, 3, 4]

Inorder of tree1 = [1,2,4]; inorder of tree2 = [0,1,3]. Merge → [0,1,1,2,3,4].

tree1 inorder (sorted, comma-separated)

tree2 inorder (sorted, comma-separated)

def get_all_elements(root1, root2):
    def inorder(node, out):
        if not node: return
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)
    a, b = [], []
    inorder(root1, a); inorder(root2, b)
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: out.append(a[i]); i += 1
        else:             out.append(b[j]); j += 1
    out.extend(a[i:]); out.extend(b[j:])
    return out

function getAllElements(root1, root2) {
  const inorder = (node, out) => {
    if (!node) return;
    inorder(node.left, out);
    out.push(node.val);
    inorder(node.right, out);
  };
  const a = [], b = [];
  inorder(root1, a); inorder(root2, b);
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) out.push(a[i++]);
    else out.push(b[j++]);
  }
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
        inorder(root1, a); inorder(root2, b);
        List<Integer> out = new ArrayList<>();
        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;
    }
    private void inorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        inorder(n.left, out);
        out.add(n.val);
        inorder(n.right, out);
    }
}

void inorder(TreeNode* n, vector<int>& out) {
    if (!n) return;
    inorder(n->left, out);
    out.push_back(n->val);
    inorder(n->right, out);
}
vector<int> getAllElements(TreeNode* r1, TreeNode* r2) {
    vector<int> a, b, out;
    inorder(r1, a); inorder(r2, b);
    int i = 0, j = 0;
    while (i < (int)a.size() && j < (int)b.size()) {
        if (a[i] <= b[j]) out.push_back(a[i++]);
        else out.push_back(b[j++]);
    }
    while (i < (int)a.size()) out.push_back(a[i++]);
    while (j < (int)b.size()) out.push_back(b[j++]);
    return out;
}

Explanation

The trick is to use a fact about binary search trees: visiting them in-order (left, node, right) hands back the values already sorted. So each tree becomes a sorted list for free.

The function inorder does exactly that, filling a list a for the first tree and b for the second. Now we have two sorted arrays and just need to combine them into one sorted array.

That is the classic merge step from mergesort. We keep two pointers i and j and repeatedly take whichever front element is smaller, advancing that pointer.

When one list runs out, we simply dump the rest of the other list onto the end, since it is already sorted.

Example: a = [1,2,4], b = [0,1,3]. We pick 0, then 1 (from a), then 1 (from b), then 2, 3, 4 — giving [0,1,1,2,3,4].

Time: O(n + m) Space: O(n + m)