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.
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
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.