# LeetCode 617: Merge Two Binary Trees

## Problem Restatement

We are given two binary trees: `root1` and `root2`.

We need to merge them into a single binary tree.

The merge rule is:

| Case | Result |
|---|---|
| Both nodes exist | Sum their values |
| One node is null | Use the non-null node |
| Both null | Result is null |

We return the merged tree as the new root.

The official problem defines merging two binary trees by summing overlapping nodes and using the non-null node when only one exists. ([leetcode.com](https://leetcode.com/problems/merge-two-binary-trees/?utm_source=chatgpt.com))

## Input and Output

Function signature:

```python
def mergeTrees(root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
    ...
```

Input:

| Parameter | Meaning |
|---|---|
| `root1` | First binary tree |
| `root2` | Second binary tree |

Output:

| Type | Meaning |
|---|---|
| `TreeNode` | Root of merged tree |

## Example

Tree 1:

```text
    1
   / \
  3   2
 /
5
```

Tree 2:

```text
    2
   / \
  1   3
   \   \
    4   7
```

Merged tree:

| Operation | Result |
|---|---|
| 1 + 2 | 3 |
| 3 + 1 | 4 |
| 2 + 3 | 5 |
| 5 | 5 |
| 4 | 4 |
| 7 | 7 |

Result:

```text
      3
     / \
    4   5
   / \   \
  5   4   7
```

## First Thought: Modify One Tree

A simple idea is to merge `root2` into `root1` directly.

If both nodes exist, we update `root1.val`.

If only one exists, we attach it.

This avoids creating a new tree.

## Key Insight

This is a classic DFS tree recursion problem.

At every pair of nodes:

| Condition | Action |
|---|---|
| both nodes exist | merge values |
| only one exists | return that node |
| both null | return null |

We apply this recursively to left and right children.

## Algorithm

For each pair of nodes `(n1, n2)`:

1. If `n1` is null, return `n2`.
2. If `n2` is null, return `n1`.
3. Otherwise:
   - Sum values: `n1.val += n2.val`
   - Merge left children
   - Merge right children
4. Return `n1` as the merged root.

## Implementation

```python
from typing import Optional

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: Optional[TreeNode],
        root2: Optional[TreeNode]
    ) -> Optional[TreeNode]:

        if not root1:
            return root2

        if not root2:
            return root1

        root1.val += root2.val

        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1
```

## Code Explanation

We first handle base cases:

```python
if not root1:
    return root2

if not root2:
    return root1
```

This means:

| Case | Meaning |
|---|---|
| root1 is null | Use root2 directly |
| root2 is null | Use root1 directly |

If both nodes exist, we merge their values:

```python
root1.val += root2.val
```

Then we recursively merge the left subtree:

```python
root1.left = self.mergeTrees(root1.left, root2.left)
```

And the right subtree:

```python
root1.right = self.mergeTrees(root1.right, root2.right)
```

Finally, we return the updated `root1`.

## Correctness

The algorithm processes both trees in parallel using DFS.

For each pair of nodes at the same position:

| Case | Behavior |
|---|---|
| both nodes exist | values are added |
| one node missing | existing subtree is reused |
| both missing | recursion returns null |

Because recursion explores left and right subtrees independently, every node in both trees is visited exactly once.

The merge operation is applied exactly once per overlapping node pair, ensuring correct accumulation of values.

Non-overlapping nodes are preserved without modification.

Therefore, the resulting tree correctly represents the merged structure defined by the problem.

## Complexity

Let `n` be the number of nodes in `root1`, and `m` be the number of nodes in `root2`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(min(n, m))` | Each overlapping node pair is visited once |
| Space | `O(h)` | Recursion stack depth equals tree height |

Worst case space:

| Tree Shape | Space |
|---|---|
| Balanced | `O(log n)` |
| Skewed | `O(n)` |

## Alternative: Create New Tree

We can also build a new tree instead of modifying `root1`.

```python
class Solution:
    def mergeTrees(
        self,
        root1: Optional[TreeNode],
        root2: Optional[TreeNode]
    ) -> Optional[TreeNode]:

        if not root1 and not root2:
            return None

        val1 = root1.val if root1 else 0
        val2 = root2.val if root2 else 0

        new_root = TreeNode(val1 + val2)

        new_root.left = self.mergeTrees(
            root1.left if root1 else None,
            root2.left if root2 else None
        )

        new_root.right = self.mergeTrees(
            root1.right if root1 else None,
            root2.right if root2 else None
        )

        return new_root
```

This version avoids mutating inputs but uses slightly more memory.

## Testing

```python
def run_tests():
    s = Solution()

    t1 = TreeNode(1,
        TreeNode(3, TreeNode(5)),
        TreeNode(2)
    )

    t2 = TreeNode(2,
        TreeNode(1, None, TreeNode(4)),
        TreeNode(3, None, TreeNode(7))
    )

    merged = s.mergeTrees(t1, t2)

    assert merged.val == 3
    assert merged.left.val == 4
    assert merged.right.val == 5
    assert merged.left.left.val == 5
    assert merged.left.right.val == 4
    assert merged.right.right.val == 7

    t3 = None
    t4 = TreeNode(1)

    assert s.mergeTrees(t3, t4).val == 1

    print("all tests passed")

run_tests()
```

Test coverage:

| Case | Why |
|---|---|
| Overlapping trees | Confirms value merging |
| Uneven structure | Confirms subtree reuse |
| One empty tree | Confirms base case handling |