Leetcode 617. Merge Two Binary Trees

Problem

You are given two binary trees represented by their root nodes. Your task is to create a new binary tree by combining these two trees using the following rules:

• When both trees have a node at the same position, create a new node with a value equal to the sum of the two node values
• When only one tree has a node at a position (the other is null), use that node in the resulting tree
• When both positions are null, the result is also null

Return the root of the newly merged tree.

Requirements

1. Process both trees simultaneously, visiting corresponding positions
2. Create new nodes in the merged tree with summed values where both input nodes exist
3. When only one input node exists at a position, include it in the result
4. Handle cases where one or both input trees are empty
5. Return the root of the merged tree

Constraints

• The number of nodes in both trees is in the range [0, 2000]
• -10^4 ≤= Node.val ≤= 10^4
• You may modify the input trees or create a new tree

Examples

Example 1:

` Input: Tree 1: Tree 2: 1 2 / \ /
3 2 1 3 / \
5 4 7

Output: 3 /
4 5 / \
5 4 7

Explanation: Overlapping nodes are summed (1+2=3, 3+1=4, 2+3=5). Non-overlapping nodes are included as-is. `

Example 2:

` Input: Tree 1: [1] Tree 2: [1, 2]

Output: [2, 2]

Explanation: The roots overlap and sum to 2. Tree 2's left child (2) is included in the result. `

Example 3:

` Input: Tree 1: [] Tree 2: [3, 5, 8]

Output: [3, 5, 8]

Explanation: When one tree is empty, return the other tree. `

Hint 1: Traversal Strategy Consider using a recursive depth-first approach where you process both trees simultaneously. At each recursive call, you're examining corresponding nodes from both trees.

Hint 2: Base Cases Think about what happens when one or both nodes are null. These are your base cases:

• If both nodes are null, return null
• If only one node is null, return the other node (no need to continue recursing down that path)
• If both nodes exist, create a new node with their summed values

Hint 3: Recursive Structure For each position, create a new node with the appropriate value, then recursively process the left children together and the right children together. The recursive calls will handle all descendants.

Full Solution ` class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

def mergeTrees(root1: TreeNode, root2: TreeNode) -> TreeNode: # Base case: if both nodes are null, return null if not root1 and not root2: return None

# If one tree is null at this position, return the other tree
# No need to continue recursing since there's no overlap
if not root1:
    return root2
if not root2:
    return root1

# Both nodes exist, so create a new node with summed values
merged = TreeNode(root1.val + root2.val)

# Recursively merge the left subtrees
merged.left = mergeTrees(root1.left, root2.left)

# Recursively merge the right subtrees
merged.right = mergeTrees(root1.right, root2.right)

return merged

`

Approach Explanation:

The solution uses a recursive depth-first traversal that processes both trees simultaneously:

1. Base Cases: Handle null nodes appropriately

   • If both nodes are null, there's nothing to merge
   • If only one node is null, we can directly use the other subtree without further recursion

2. Recursive Case: When both nodes exist

   • Create a new node with the sum of both values
   • Recursively merge the left children of both nodes
   • Recursively merge the right children of both nodes

3. Tree Construction: The recursion naturally builds the merged tree from bottom to top as the call stack unwinds

Alternative Approach - Modify in Place:

Instead of creating a new tree, you could modify root1 in place:

` def mergeTrees(root1: TreeNode, root2: TreeNode) -> TreeNode: if not root1: return root2 if not root2: return root1

# Modify root1 in place
root1.val += root2.val
root1.left = mergeTrees(root1.left, root2.left)
root1.right = mergeTrees(root1.right, root2.right)

return root1

`

Iterative Approach Using Stack:

` def mergeTrees(root1: TreeNode, root2: TreeNode) -> TreeNode: if not root1: return root2

# Use a stack to simulate recursion
stack = [(root1, root2)]

while stack:
    node1, node2 = stack.pop()
    
    # If node2 is null, node1 already has correct structure
    if not node2:
        continue
    
    # Add node2's value to node1
    node1.val += node2.val
    
    # Process left children
    if not node1.left:
        node1.left = node2.left
    else:
        stack.append((node1.left, node2.left))
    
    # Process right children
    if not node1.right:
        node1.right = node2.right
    else:
        stack.append((node1.right, node2.right))

return root1

`

Complexity Analysis:

• Time Complexity: O(min(m, n)) where m and n are the number of nodes in the two trees. We visit each overlapping position once. In the worst case where trees are identical in structure, this becomes O(n).

• Space Complexity:

  • Recursive approach: O(h) where h is the height of the shorter tree (call stack space)
  • Iterative approach: O(h) for the explicit stack
  • Creating new tree adds O(min(m, n)) space for the new nodes