Merge Two Binary Trees | Leetcode 617

Welcome to our multi-approach guide for Merge Two Binary Trees (Leetcode 617). This problem is a phenomenal exercise in understanding structural traversal, giving you the perfect opportunity to practice both standard DFS recursion and robust iterative structures.

Problem Statement

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] Output: [3,4,5,5,4,null,7] (The roots [1] and [2] merge into [3]. The left children [3] and [1] merge into [4]. The right children [2] and [3] merge into [5], etc).

Approach 1: Recursive Preorder Traversal (DFS)

Recursion is almost always the cleanest way to traverse a standard binary tree.

In a preorder traverse, we evaluate the current node before exploring its children. We can simply write a function that takes two node references t1 and t2.

• If t1 is null, we return t2.
• If t2 is null, we return t1.
• If both exist, we add their values together and permanently attach that sum to t1! (Modifying the first tree in-place saves memory). Then, we recursively call the left and right children.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, t1: Optional[TreeNode], t2: Optional[TreeNode]) -> Optional[TreeNode]:
        # Base Cases: If one node is entirely missing, just return the entire structural branch of the other!
        if not t1:
            return t2
        if not t2:
            return t1
            
        # Standard Preorder: Evaluate Root node first
        t1.val = t1.val + t2.val
        
        # Traverse Left and Right heavily relying on the recursive stack
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)
        
        return t1

Complexity Analysis

Approach 2: Iterative Traversal using Breadth-First-Search (BFS)

While the recursive stack handles state tracking for you passively, recursion can crash a system if the tree is astronomically deep. To avoid a RecursionError or a StackOverflowException, production environments often require expanding problems iteratively flat.

We can solve this iteratively Level-by-Level using a dual-node Queue. We push pairs of [t1, t2] to the Queue. As we pop them off, we sum the overlapping values and handle appending missing structural children.

graph TD
    A["Initial Queue:[(root1, root2)]"]
    B{"Queue Empty?"}
    
    C["Pop (node1, node2)"]
    D["node1.val += node2.val"]
    
    E{"Has Both Lefts?"}
    F["Push (L1, L2) to Queue"]
    
    G{"Left1 Missing? Left2 Exists?"}
    H["node1.left = node2.left"]
    
    A --> B
    B -- "No" --> C
    C --> D
    D --> E
    E -- "Yes" --> F
    E -- "No" --> G
    G -- "Yes" --> H
    
    style H fill:#4CAF50,stroke:#fff,stroke-width:2px,color:#fff

from collections import deque

class Solution:
    def mergeTrees(self, t1: Optional[TreeNode], t2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not t1: return t2
        if not t2: return t1
        
        # Initialize a Double Ended Queue
        q = deque([(t1, t2)])
        
        while q:
            n1, n2 = q.popleft()
            
            # Sum the current node execution
            n1.val += n2.val
            
            # Left Child handling
            if n1.left and n2.left:
                q.append((n1.left, n2.left))
            elif not n1.left and n2.left:
                n1.left = n2.left
                
            # Right Child handling
            if n1.right and n2.right:
                q.append((n1.right, n2.right))
            elif not n1.right and n2.right:
                n1.right = n2.right
                
        return t1

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (617)