Merge Two Binary Trees — LeetCode 617 Recursive Overlay

Problem Statement#

Given two binary trees root1 and root2, merge them so that overlapping nodes sum and non-overlapping nodes are taken as is. Return the merged tree.

Constraints:

• Number of nodes in either tree is in the range [0, 2000].
• -10^4 <= Node.val <= 10^4.

Input:  root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Input:  root1 = [1], root2 = [1,2]
Output: [2,2]

Why This Problem Matters#

LeetCode 617 — Merge Two Binary Trees is a friendly Easy that interviewers at Amazon, Apple, Meta, and Microsoft use to test parallel-recursion comfort and to surface a subtle memory question: do you allocate a fresh tree or reuse the inputs?

Engineers who blindly call new TreeNode(...) use O(n) extra memory; engineers who reuse root1 use O(h). That single design choice can flip the interview signal from "knows recursion" to "knows memory budgets". Many tier-1 engineers fail this exact subtlety on phone screens.

The pattern (parallel DFS over two trees with null handling) generalises directly to Same Tree, Symmetric Tree, Flip Equivalent, Subtree of Another Tree, and any zip-like operation on trees.

The Core Insight#

At every position, four cases:

1. Both null -> result is null.
2. root1 null -> result is root2 (no work).
3. root2 null -> result is root1 (no work).
4. Both non-null -> sum values, recurse on both lefts and both rights.

Reusing one of the inputs (commonly root1) avoids any allocations and keeps space at O(h) recursion. State this trade-off explicitly during the interview.

Visual Dry Run#

root1 = [1, 3, 2, 5], root2 = [2, 1, 3, null, 4, null, 7]

Merged tree: [3, 4, 5, 5, 4, null, 7].

Solution (Optimal)#

# Python — reuse root1 to keep memory at O(h)
class Solution:
    def mergeTrees(self, root1, root2):
        if not root1: return root2  # reuse root2 wholesale
        if not root2: return root1  # reuse root1 wholesale
        root1.val += root2.val
        root1.left  = self.mergeTrees(root1.left,  root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

// JavaScript — same pattern
var mergeTrees = function(r1, r2) {
    if (!r1) return r2;
    if (!r2) return r1;
    r1.val += r2.val;
    r1.left  = mergeTrees(r1.left,  r2.left);
    r1.right = mergeTrees(r1.right, r2.right);
    return r1;
};

# Iterative BFS using paired stack — useful for very deep skewed trees
class Solution:
    def mergeTrees(self, r1, r2):
        if not r1: return r2
        if not r2: return r1
        stack = [(r1, r2)]
        while stack:
            a, b = stack.pop()
            if not a or not b: continue
            a.val += b.val
            if not a.left:  a.left  = b.left
            else: stack.append((a.left,  b.left))
            if not a.right: a.right = b.right
            else: stack.append((a.right, b.right))
        return r1

Time: O(n) where n is the size of the smaller tree (we short-circuit when one side is null). Space: O(h) recursion stack. The input trees are mutated, so allocation is O(1).

Common Mistakes#

• Allocating new TreeNode for every position instead of reusing — turns O(h) memory into O(n) and is flagged in code review.
• Forgetting the null short-circuit and crashing on root2.val when root2 is null.
• Returning a freshly constructed root with val = root1.val + root2.val but stale child pointers.
• Modifying root1 and then continuing to read original root1 values elsewhere in the caller.

Interview Tips#

• Ask "is mutation okay?" — if yes, reuse the input; if no, allocate new nodes.
• Reusing root1 keeps memory at O(h); allocating fresh nodes costs O(n).
• Mention the iterative variant for very deep skewed trees.
• Sketch a 3-level tree where one side has more depth so the interviewer sees the reuse cases.

Follow-up Questions#

• Without mutation? Allocate new TreeNode(a.val + b.val) each time and recurse.
• Merging k trees? Pairwise merge in a loop or use heap to balance.
• Merge two BSTs preserving the BST property? Inorder both, merge sorted, rebuild.
• Operate on n-ary trees? Recurse over zipped children lists.
• Stream the second tree? Build a serialized form and walk inorder.

Key Takeaways#

• LeetCode 617 Merge Two Binary Trees runs in O(n) time and O(h) space.
• The pattern is parallel DFS with three null cases: both null, one null (reuse), both non-null (sum + recurse).
• Reusing one of the inputs is the standard trick to keep allocations O(1).
• Asked at Amazon, Apple, Meta, Microsoft, Google as a parallel-recursion warmup.
• Foundation for Same Tree (LC 100), Symmetric Tree (LC 101), Flip Equivalent (LC 951).
• Iterative paired-stack version handles skewed trees safely.
• Always ask about mutation vs. immutability before coding.