Merge Two Binary Trees: Recursive DFS in One Pass

You are given two binary trees. Imagine overlaying them on top of each other. Where both trees have a node, the merged node's value is the sum of both values. Where only one tree has a node, that node becomes part of the merged tree as-is.

This is LeetCode 617: Merge Two Binary Trees, and it is one of the best introductions to working with two trees simultaneously. The problem forces you to think about three cases at every position: both nodes exist, only one exists, or neither exists.

Why this problem matters

Most tree problems give you a single tree and ask you to traverse or transform it. Merge Two Binary Trees is different because you are walking two trees at the same time, in lockstep. At every recursive call, you have two nodes (or nulls) to consider, and you need to decide what to do based on which ones exist.

This "parallel traversal" pattern shows up in other tree problems like Same Tree and Symmetric Tree. If you can merge two trees, you already understand the mechanics of comparing or combining them.

The key insight

At every position in the tree, there are only three possibilities:

1. Both nodes exist: sum their values and recurse into both pairs of children.
2. Only one node exists: return that node (and its entire subtree) directly.
3. Neither node exists: return None.

That is the entire algorithm. You walk both trees in the same order (pre-order DFS works well) and apply these three rules at each step. The recursion handles the rest.

The recursive solution

def merge_trees(t1, t2):
    if t1 is None:
        return t2
    if t2 is None:
        return t1
    t1.val += t2.val
    t1.left = merge_trees(t1.left, t2.left)
    t1.right = merge_trees(t1.right, t2.right)
    return t1

Let's break this down line by line:

• if t1 is None: return t2 handles the case where the first tree has no node at this position. Whatever the second tree has (a node or None), that is the answer.
• if t2 is None: return t1 handles the mirror case. If the second tree is missing, keep the first tree's node.
• t1.val += t2.val is the merge step. Both nodes exist, so we add their values. We are reusing t1 as the merged tree.
• The two recursive calls merge the left children together and the right children together, then attach the results.

The function returns t1, which now contains the fully merged tree.

Step-by-step walkthrough

Let's trace through the merge of two example trees. Tree 1 has root 1, left child 3 (with left grandchild 5), and right child 2. Tree 2 has root 2, left child 1 (with right grandchild 4), and right child 3 (with right grandchild 7).

Notice how the recursion naturally handles asymmetry. When one tree has a child but the other does not, we just return the existing subtree. There is no need for special-case logic beyond the two null checks at the top of the function.

Complexity analysis

Time: we visit each overlapping node exactly once. In the worst case, both trees have the same shape and we visit all nodes. But if one tree is smaller, we stop recursing once we hit a null in the smaller tree and just attach the remaining subtree from the larger tree.

Space: the call stack depth equals the height of the shorter tree's overlap with the longer one. For a balanced tree, this is O(log n). For a completely skewed tree, it could be O(n).

Edge cases to watch for

• Both trees are None: the first null check returns t2, which is also None. Correct.
• One tree is completely empty: if t1 is None, you return the entire t2 tree. If t2 is None, you return the entire t1 tree. No recursion needed.
• Trees with different shapes: the null checks handle this naturally. Wherever one tree has a subtree and the other does not, the existing subtree is reused without further traversal.
• Single-node trees: both have just a root. The values are summed, and both recursive calls hit None immediately.

The building blocks

This problem uses two fundamental building blocks:

1. Recursive null base case. The skeleton of "if null, return; otherwise process and recurse into children" is the same pattern you see in Maximum Depth, Invert Binary Tree, Same Tree, and dozens of others. Here the base case returns the other tree's node (or None if both are null), rather than returning 0 or True.

2. Parallel tree traversal. Instead of walking one tree, you walk two trees in lockstep. Each recursive call takes a pair of nodes (t1, t2) and processes them together. This same pattern appears in Same Tree (comparing values) and Symmetric Tree (comparing mirror positions). The merge operation is just one specific way to combine the two nodes.

# The general pattern for parallel tree traversal:
def solve(t1, t2):
    if t1 is None and t2 is None:
        return None
    if t1 is None:
        return handle_only_t2(t2)
    if t2 is None:
        return handle_only_t1(t1)
    # both exist: combine and recurse
    result = combine(t1, t2)
    result.left = solve(t1.left, t2.left)
    result.right = solve(t1.right, t2.right)
    return result

For Merge Two Binary Trees, combine means summing the values. For Same Tree, it means checking equality. The skeleton stays the same.

From understanding to recall

You just traced through a recursive merge and saw exactly how two trees are walked in parallel. The logic is clean: two null checks at the top, a sum in the middle, and two recursive calls. It makes sense right now.

But understanding is not the same as recall. In an interview, you need to write this from memory under pressure. Can you reconstruct the three cases (both null, one null, both present) without looking? Can you remember which node to return in each null case?

Spaced repetition builds that recall. You practice writing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each rep strengthens the pattern until the parallel tree traversal skeleton becomes automatic.

The parallel traversal pattern and the recursive null base case show up across many tree problems. Drilling them individually with spaced repetition is far more efficient than solving random problems and hoping the connections stick.

Related posts

• Invert Binary Tree - Another tree transformation problem using the same recursive null base case pattern, but swapping children instead of merging
• Same Tree - Uses the parallel tree traversal pattern to compare two trees for equality instead of merging them
• Symmetric Tree - Walks two subtrees in mirror order using the same dual-node recursion approach