617 · Merge Two Binary Trees

Sub-variant B where the return is a node instead of a boolean. The interesting consequence: the three base cases of LC 100 collapse into two, because returning "the other side" happens to be right in both of the null cases.

1 — The problem

Overlay two trees. Where both have a node, sum the values; where only one does, use it as-is. Same lockstep descent as LC 100 — two cursors, moved together — but the recursion now produces structure rather than a verdict.

Rows one and two share an answer, so if (a == null) return b; handles both. That is a small piece of luck rather than a principle — it works because null is the correct merge of nothing with nothing, and also the correct merge of nothing with something.

2 — Grafting whole subtrees

Watch node 3 in tree a: tree b has nothing there, so the recursion returns 3 untouched and stops — it does not walk into it. Whole subtrees are adopted in O(1).

2.1 It mutates a

Line 4 writes into the first tree, and lines 5–6 rewire its children. When this returns, tree a no longer exists in its original form, and tree b's nodes are now shared into it. LeetCode accepts this, and it is the reason the solution is six lines.

If the inputs must survive, allocate instead — and note the base cases now need care, because returning b would alias it:

TreeNode merge(TreeNode a, TreeNode b) {
    if (a == null && b == null) return null;
    int v = (a == null ? 0 : a.val) + (b == null ? 0 : b.val);
    TreeNode nd = new TreeNode(v);
    nd.left  = merge(a == null ? null : a.left,  b == null ? null : b.left);
    nd.right = merge(a == null ? null : a.right, b == null ? null : b.right);
    return nd;
}

Longer, and it loses the O(1) subtree graft — every node of every surviving subtree gets copied. That trade is worth naming out loud if an interviewer asks about mutation.

2.2 What this rep is for

If LC 100 is solid, this teaches one new thing: that a two-cursor recursion can return anything, not just a verdict. That is worth ten minutes and not more — the bundle marks it optional for exactly that reason.

3 — Complexity and edge cases

• Time O(min(m, n)) — the recursion only descends where both trees have nodes; everywhere else it grafts in O(1). Space O(min(m, n)) for the stack.
• Both empty: null.
• One empty: the other, returned whole and unvisited.
• Disjoint shapes: the merge is the union, with no addition anywhere.
• Negative values are fine; nothing here assumes signs.
• Common bug: if (a == null && b == null) return null; followed by dereferencing a.val — the single-null case is still live.
• Common bug: forgetting to assign the results back to a.left / a.right. The values merge and the structure does not, which looks almost right.

4 — Reference implementation

public TreeNode mergeTrees(TreeNode a, TreeNode b) {
    if (a == null) return b;      // covers "both null" too
    if (b == null) return a;      // graft the rest of a, unvisited
    a.val += b.val;
    a.left  = mergeTrees(a.left,  b.left);
    a.right = mergeTrees(a.right, b.right);
    return a;
}