Merge two BSTs

Medium

Problem

Given two BSTs, return all of their values combined in sorted order, or build a single balanced BST from them. Aim for O(m + n) time.

Example 1

Input:  BST1 = [3, 1, 5], BST2 = [4, 2, 6]
Output: [1, 2, 3, 4, 5, 6]

Also asked as: Merge two BST

Test cases

No automated tests for this problem yet. Use the examples above to check your output.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

This problem has no automated tests. Run executes your code and shows what it logs.

View solutionHide solution1 approach

1. In-order lists → merge → build balanced BST

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

In-order traversal of each BST gives two sorted arrays; merge them, then build a height-balanced BST from the merged array.

function mergeBSTs(a, b) {
const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };
const A = inorder(a), B = inorder(b);
const merged = [];
let i = 0, j = 0;
while (i < A.length && j < B.length) merged.push(A[i] <= B[j] ? A[i++] : B[j++]);
while (i < A.length) merged.push(A[i++]);
while (j < B.length) merged.push(B[j++]);
const build = (lo, hi) => lo > hi ? null : (() => { const m = (lo + hi) >> 1; return { val: merged[m], left: build(lo, m - 1), right: build(m + 1, hi) }; })();
return build(0, merged.length - 1);
}