Merge Two Binary Trees
Overlay two binary trees, summing values where both trees have a node.
- The number of nodes in both trees is in the range [0, 2000].
- -10⁴ <= Node.val <= 10⁴
Intuition
Merge two binary trees overlays two trees, summing values where both have a node and keeping whichever node exists where only one does. The recursion is short, and there is exactly one trap.
The tempting shortcut is to return null as soon as either node is missing. That is wrong, and the reason is worth stating plainly. If root1 is null, the correct result is the whole of root2's subtree carried over unchanged — not nothing. Returning null there silently deletes an entire branch of the output.
So the merge needs three cases rather than two:
- Both null gives null; exactly one null means take that subtree whole; both present means sum the values and merge the children.
The middle case is where the saving is. When one side is missing, the surviving subtree needs no traversal at all — it is simply reattached as-is. There is nothing to merge it with, so recursing into it would be wasted work.
Writing it as if not root1: return root2 followed by if not root2: return root1 handles both the one-missing and both-missing cases correctly: when both are null, the first line returns root2, which is null. The three cases collapse into two lines without any explicit both-null check.
The problem permits mutating one input tree in place, which avoids allocating new nodes — worth mentioning, though building a fresh tree is cleaner if the inputs must be preserved.
Recurse in parallel down both trees. When one side is null the other subtree is grafted in whole — no further recursion needed, since there's nothing to merge it with. That early return is what keeps the traversal proportional to the overlap.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(min(m, n)) time and O(min(m, n)) space.
Reject the two-case shortcut
Returning null when either node is missing discards the surviving subtree entirely. If root1 is null the answer is all of root2, not nothing — this is the one bug this problem is built around.
Return the other tree when one is null
if not root1: return root2 and if not root2: return root1. The surviving subtree is reattached whole, with no recursion into it — there is nothing to merge it against, so traversing it would be pointless.
Let both-null fall out naturally
When both are null, the first check returns root2, which is null — the correct answer. No explicit both-null case is needed, which is why two lines cover three situations.
Sum the values when both exist
Create or reuse a node holding root1.val + root2.val. This is the only case where arithmetic happens; the others are pure structural carry-over.
Merge the children pairwise
Recurse on (root1.left, root2.left) and (root1.right, root2.right), assigning the results. Pairing left with left preserves position — pairing left with right would produce a mirrored merge.
Cost of the traversal
Only the overlapping region is traversed, since a one-sided subtree is reattached without recursion. That gives O(min(n, m)) time and O(h) space for the recursion stack — better than the O(n + m) it first appears to need.
Solution & live demo
Common pitfalls
Continuing to recurse after one side is null
if not root1:
merged = TreeNode(root2.val)
merged.left = self.mergeTrees(None, root2.left)if not root1:
return root2Rebuilding the remaining subtree node by node is pure waste — it's already exactly the answer for that branch. Returning it directly is both faster and shorter.
Testing the null cases in the wrong order
if not root1: return root2 if not root1 and not root2: return None
if not root1 and not root2: return None if not root1: return root2
The second condition is unreachable once the first has fired. As written it happens to be harmless — root2 is null so returning it is still correct — but the ordering hides the intent and breaks if the branches ever diverge.
Mutating root1 in place
root1.val += root2.val return root1
merged = TreeNode(root1.val + root2.val)
Accepted by most judges, but it destroys the caller's input tree. Building a new node leaves both arguments intact, which matters if either is reused.
Edge cases
Falls through both null checks and returns None.
The other tree is returned unchanged, no merging performed.
Where one side runs out first, remaining nodes are reattached as-is via the single-null case.
Sum still works correctly; no special casing needed.