LeetCode 617: Merge Two Binary Trees Solution in Python – A Step-by-Step Guide

What Is LeetCode 617: Merge Two Binary Trees?

In LeetCode 617: Merge Two Binary Trees, you’re given two binary trees, each defined by a root node with val, left, and right attributes. Your task is to merge them into a single binary tree where:

• If nodes overlap (same position), their values are summed.
• If a node exists in one tree but not the other, it’s included as is in the merged tree.

For example, merging trees [1,3,2,5] (1->3(left), 1->2(right), 3->5(left)) and [2,1,3,null,4,null,7] results in a tree with summed values where nodes align. This problem tests your ability to traverse and manipulate binary trees.

Problem Statement

• Input: Two binary tree roots, root1 and root2.
• Output: The root of a merged binary tree.
• Rules:
• Overlapping nodes: Sum their values.
• Non-overlapping nodes: Use the existing node.
• Return the merged tree’s root.

Constraints

• Number of nodes in each tree: 0 to 2000.
• -10⁴ ≤ Node.val ≤ 10⁴.

Examples

• Input:
• root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
• Tree 1: 1->3(left), 1->2(right), 3->5(left).
• Tree 2: 2->1(left), 2->3(right), 1->4(right), 3->7(right).
• Output: [3,4,5,5,4,null,7]
• Root: 1+2=3, left: 3+1=4, right: 2+3=5, etc.
• Input:
• root1 = [1], root2 = [1,2]
• Output: [2,2] (1+1=2, 2 from root2’s left)
• Input:
• root1 = [], root2 = [1]
• Output: [1]

These examples show the merging—let’s solve it!

Understanding the Problem: Merging Trees

To solve LeetCode 617: Merge Two Binary Trees in Python, we need to combine two trees by traversing them simultaneously, summing values at overlapping positions, and preserving non-overlapping nodes. A naive approach might rebuild the tree from scratch, but we can merge in place. We’ll use:

• Best Solution (Recursive Merging): O(n) time, O(h) space—n is total nodes, h is height—simple and natural.
• Alternative Solution (Iterative Stack): O(n) time, O(n) space—explicit and controlled.

Let’s start with the recursive solution, breaking it down for beginners.

Best Solution: Recursive Merging

Why This Is the Best Solution

The recursive merging approach is the top choice for LeetCode 617 because it’s efficient—O(n) time to visit each node—and leverages the natural recursive structure of binary trees, making it both concise and intuitive. It modifies one tree in place, minimizing space to O(h) for the call stack. It’s like stitching two trees together branch by branch!

How It Works

Think of this as zipping two trees together:

• Step 1: Base Cases:
• If root1 is null, return root2.
• If root2 is null, return root1.
• Step 2: Merge Roots:
• Sum root1.val and root2.val, store in root1.
• Step 3: Recurse on Children:
• Merge left subtrees: root1.left = merge(root1.left, root2.left).
• Merge right subtrees: root1.right = merge(root1.right, root2.right).
• Step 4: Return Merged Root:
• Return root1 as the merged tree.

It’s like a tree fusion dance—root first, then kids!

Step-by-Step Example

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

• Root:
• root1.val = 1, root2.val = 2.
• root1.val = 1 + 2 = 3.
• Left:
• root1.left = 3, root2.left = 1.
• root1.left.val = 3 + 1 = 4.
• root1.left.left = 5, root2.left.right = 4.
• root1.left.left = 5 + null = 5.
• root1.left.right = null + 4 = 4.
• Right:
• root1.right = 2, root2.right = 3.
• root1.right.val = 2 + 3 = 5.
• root1.right.right = null, root2.right.right = 7.
• root1.right.right = null + 7 = 7.
• Output: [3,4,5,5,4,null,7].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

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, root1: TreeNode, root2: TreeNode) -> TreeNode:
        # Step 1: Base cases
        if not root1:
            return root2
        if not root2:
            return root1

        # Step 2: Merge current nodes
        root1.val += root2.val

        # Step 3: Recursively merge children
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        # Step 4: Return merged root
        return root1

• Lines 1-5: TreeNode class (standard).
• Lines 10-13: Base cases:
• Return non-null tree if one is null.
• Line 16: Sum values at current nodes.
• Lines 19-20: Recurse:
• Merge left and right subtrees.
• Time Complexity: O(n)—n is min nodes in both trees (visits overlapping nodes).
• Space Complexity: O(h)—recursion stack (h = height).

This is like a tree zipper—clean and fast!

Alternative Solution: Iterative Stack-Based Approach

Why an Alternative Approach?

The iterative stack-based approach uses a stack to merge trees—O(n) time, O(n) space. It avoids recursion, giving explicit control, and is useful if stack depth is a concern (though rare here). It’s like manually stitching trees with a checklist!

How It Works

Picture this as a tree walk with a stack:

• Step 1: Push root pair onto stack.
• Step 2: Process stack:
• Pop pair, sum values if both exist.
• Push left and right child pairs.
• Handle null cases by attaching non-null children.
• Step 3: Continue until stack is empty.
• Step 4: Return merged root.

It’s like a step-by-step tree merge!

Step-by-Step Example

Example: root1 = [1,3], root2 = [2,1,3]

• Init: Stack = [(1, 2)], root1.val = 1+2 = 3.
• Pop (3, 2):
• Left: (3.left=3, 2.left=1), push, 3.left.val = 3+1 = 4.
• Right: (3.right=null, 2.right=3), 3.right = 2.right.
• Pop (4, 1):
• No children, done.
• Result: [3,4,3].

Code for Iterative Approach

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        # Step 1: Handle edge cases
        if not root1:
            return root2
        if not root2:
            return root1

        # Step 2: Initialize stack with root pair
        stack = [(root1, root2)]

        # Step 3: Process stack
        while stack:
            node1, node2 = stack.pop()

            # Sum values
            node1.val += node2.val

            # Merge left children
            if node1.left and node2.left:
                stack.append((node1.left, node2.left))
            elif not node1.left:
                node1.left = node2.left

            # Merge right children
            if node1.right and node2.right:
                stack.append((node1.right, node2.right))
            elif not node1.right:
                node1.right = node2.right

        # Step 4: Return merged root
        return root1

• Lines 4-7: Base cases.
• Line 10: Start stack with roots.
• Lines 13-25: Process:
• Sum values, push overlapping children, attach non-null ones.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(n)—stack size.

It’s a manual tree stitch—controlled but bulkier!

Comparing the Two Solutions

• Recursive (Best):
• Pros: O(n) time, O(h) space, concise and natural.
• Cons: Recursion depth for skewed trees.
• Iterative (Alternative):
• Pros: O(n) time, O(n) space, no recursion.
• Cons: More code, higher space.

Recursive wins for elegance.

Additional Examples and Edge Cases

• Input: root1 = [1], root2 = []
• Output: [1].
• Input: root1 = [1,2], root2 = [3,null,4]
• Output: [4,2,4].

Both handle these well.

Complexity Breakdown

• Recursive: Time O(n), Space O(h).
• Iterative: Time O(n), Space O(n).

Recursive is leaner.

Key Takeaways

• Recursive: Tree flow—smart!
• Iterative: Stack control—clear!
• Trees: Merging is fun.
• Python Tip: Recursion rocks—see Python Basics.

Final Thoughts: Merge Those Trees

LeetCode 617: Merge Two Binary Trees in Python is a fun tree-combining challenge. Recursive merging offers simplicity, while iterative gives control. Want more? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 226: Invert Binary Tree. Ready to fuse? Head to Solve LeetCode 617 on LeetCode and merge those trees today!