Merge two BSTs
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.
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);}