Merge BSTs to Create Single BST

hard binary search tree hash table recursion

Problem

You are given n BST roots, each tree holding at most 3 nodes with all root values distinct. Repeatedly pick a leaf in one tree whose value equals the root value of another tree, and splice that whole tree onto the leaf. Return the root of the single valid BST formed after n − 1 such merges, or null if no valid BST is possible.

Inputtrees = [[2,1],[3,2,5],[5,4]]

Output[3,2,5,1,null,4]

Root 3 owns leaves 2 and 5. Tree (2,1) attaches at leaf 2 and tree (5,4) at leaf 5, giving one valid BST.

Inputtrees = [[5,3,8],[3,2,6]]

Output[] (null)

Attaching (3,2,6) at leaf 3 puts 6 in 5's left subtree, breaking the BST order.

trees (one per group: root,left,right — left/right optional)

def canMerge(trees):
    roots = {t.val: t for t in trees}
    leaves = Counter()
    for t in trees:
        for c in (t.left, t.right):
            if c: leaves[c.val] += 1
    start = [t for t in trees if leaves[t.val] == 0]
    if len(start) != 1: return None
    used = 0
    def build(node, lo, hi):
        nonlocal used
        if not node: return True
        if not (lo < node.val < hi): return False
        if not node.left and not node.right and node.val in roots:
            r = roots.pop(node.val); used += 1
            node.left, node.right = r.left, r.right
        return build(node.left, lo, node.val) and build(node.right, node.val, hi)
    root = start[0]; roots.pop(root.val); used += 1
    ok = build(root, float('-inf'), float('inf'))
    return root if ok and used == len(trees) else None

function canMerge(trees) {
  const roots = new Map(), leaves = new Map();
  for (const t of trees) roots.set(t.val, t);
  for (const t of trees) for (const c of [t.left, t.right])
    if (c) leaves.set(c.val, (leaves.get(c.val) || 0) + 1);
  const start = trees.filter(t => !leaves.get(t.val));
  if (start.length !== 1) return null;
  let used = 0;
  function build(node, lo, hi) {
    if (!node) return true;
    if (!(lo < node.val && node.val < hi)) return false;
    if (!node.left && !node.right && roots.has(node.val)) {
      const r = roots.get(node.val); roots.delete(node.val); used++;
      node.left = r.left; node.right = r.right;
    }
    return build(node.left, lo, node.val) && build(node.right, node.val, hi);
  }
  const root = start[0]; roots.delete(root.val); used++;
  const ok = build(root, -Infinity, Infinity);
  return ok && used === trees.length ? root : null;
}

Map<Integer, TreeNode> roots = new HashMap<>();
int used = 0;
TreeNode canMerge(List<TreeNode> trees) {
    Map<Integer, Integer> leaves = new HashMap<>();
    for (TreeNode t : trees) roots.put(t.val, t);
    for (TreeNode t : trees)
        for (TreeNode c : new TreeNode[]{t.left, t.right})
            if (c != null) leaves.merge(c.val, 1, Integer::sum);
    TreeNode start = null; int cnt = 0;
    for (TreeNode t : trees) if (!leaves.containsKey(t.val)) { start = t; cnt++; }
    if (cnt != 1) return null;
    roots.remove(start.val); used++;
    boolean ok = build(start, Long.MIN_VALUE, Long.MAX_VALUE);
    return ok && used == trees.size() ? start : null;
}
boolean build(TreeNode node, long lo, long hi) {
    if (node == null) return true;
    if (!(lo < node.val && node.val < hi)) return false;
    if (node.left == null && node.right == null && roots.containsKey(node.val)) {
        TreeNode r = roots.remove(node.val); used++;
        node.left = r.left; node.right = r.right;
    }
    return build(node.left, lo, node.val) && build(node.right, node.val, hi);
}

unordered_map<int, TreeNode*> roots;
int used = 0;
bool build(TreeNode* node, long lo, long hi) {
    if (!node) return true;
    if (!(lo < node->val && node->val < hi)) return false;
    if (!node->left && !node->right && roots.count(node->val)) {
        TreeNode* r = roots[node->val]; roots.erase(node->val); used++;
        node->left = r->left; node->right = r->right;
    }
    return build(node->left, lo, node->val) && build(node->right, node->val, hi);
}
TreeNode* canMerge(vector<TreeNode*>& trees) {
    unordered_map<int, int> leaves;
    for (auto t : trees) roots[t->val] = t;
    for (auto t : trees) for (auto c : {t->left, t->right})
        if (c) leaves[c->val]++;
    TreeNode* start = nullptr; int cnt = 0;
    for (auto t : trees) if (!leaves.count(t->val)) { start = t; cnt++; }
    if (cnt != 1) return nullptr;
    roots.erase(start->val); used++;
    bool ok = build(start, LONG_MIN, LONG_MAX);
    return ok && used == (int)trees.size() ? start : nullptr;
}

Explanation

Each tiny tree can only attach in one place: at a leaf whose value equals that tree's root. So the whole puzzle is really about which root values appear as leaves of other trees and which do not.

First build a roots map (root value → tree) and count how often each value appears as a leaf. Exactly one root must never appear as a leaf — that root is the only one nothing can attach to, so it must be the final overall root. If zero or more than one root has this property, the merge is impossible.

From that starting root we do a single recursive BST validation carrying an open interval (lo, hi). At each node we check lo < val < hi. Whenever we reach a leaf whose value is still in the roots map, we splice in that tree's children and mark the root as used. The recursion then naturally walks into the newly attached subtree under tightened bounds.

Splicing on the fly means we validate ordering and assemble the tree in one pass. If any node violates its bounds we fail immediately. Removing each root from the map as it is consumed also prevents reusing a tree twice.

Finally the answer is valid only if the recursion succeeded and every one of the n trees was consumed (used == n). A leftover tree means the input was disconnected, so we return null.

Example: [[2,1],[3,2,5],[5,4]]. Value 3 never appears as a leaf, so root 3 starts. Its leaf 2 pulls in tree (2,1) and its leaf 5 pulls in tree (5,4); all bounds hold and all 3 trees are used, yielding [3,2,5,1,null,4].

Time: O(n) Space: O(n)