Merge Two Binary Trees
Overlay two binary trees, summing values where both trees have a node.
Open on LeetCode ↗Intuition
The tempting shortcut is to return None the moment either root is None -- but that is wrong: if root1 is None, the correct answer is the WHOLE of root2's subtree carried over as-is, not nothing. Only when BOTH nodes are None does the merge truly produce None. So the recursion needs three cases, not two: both missing means None, exactly one missing means take that one whole, and both present means sum the values and merge children recursively. The surviving subtree is not touched, just reattached.
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
Handle the two 'one missing' cases explicitly
if not root1: return root2, and if not root2: return root1. These return the entire remaining subtree unchanged -- no further recursion needed on that branch.
Both present: sum and recurse
Create (or reuse) a node with root1.val + root2.val, then merge(root1.left, root2.left) and merge(root1.right, root2.right).
Both missing
If both root1 and root2 are None, return None -- this is the true base case, checked implicitly by both single-null checks passing through None on each side.
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.