# LeetCode 100: Same Tree

## Problem Restatement

We are given the roots of two binary trees:

```python
p
q
```

We need to check whether the two trees are the same.

Two binary trees are the same if:

| Requirement | Meaning |
|---|---|
| Same structure | Every node position exists in both trees or in neither tree |
| Same values | Corresponding nodes have equal values |

The official statement defines two binary trees as the same when they are structurally identical and their nodes have the same value. The constraints say both trees have between `0` and `100` nodes, and node values are between `-10^4` and `10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Roots `p` and `q` of two binary trees |
| Output | `True` if the trees are the same, otherwise `False` |
| Empty trees | Two empty trees are the same |
| Structural mismatch | One node exists while the other does not |
| Value mismatch | Corresponding nodes have different values |

Function shape:

```python
class Solution:
    def isSameTree(
        self,
        p: Optional[TreeNode],
        q: Optional[TreeNode],
    ) -> bool:
        ...
```

## Examples

Example 1:

```python
p = [1, 2, 3]
q = [1, 2, 3]
```

Both trees have the same shape and values:

```python
    1
   / \
  2   3
```

Answer:

```python
True
```

Example 2:

```python
p = [1, 2]
q = [1, None, 2]
```

Tree `p`:

```python
  1
 /
2
```

Tree `q`:

```python
1
 \
  2
```

They contain the same values, but the structure is different.

Answer:

```python
False
```

Example 3:

```python
p = [1, 2, 1]
q = [1, 1, 2]
```

The structures match, but corresponding values differ.

Answer:

```python
False
```

## First Thought: Traverse Both Trees

We need to compare the trees node by node.

At each position, there are three cases:

1. Both nodes are missing.
2. One node is missing.
3. Both nodes exist.

If both nodes are missing, that position matches.

If only one node is missing, the structure differs.

If both nodes exist, their values must match, and their left and right subtrees must also match.

This naturally gives a recursive solution.

## Key Insight

Two trees are the same if their roots match and their subtrees match.

So the condition is:

```python
same(p, q) =
    p and q are both None
    or
    p.val == q.val
    and same(p.left, q.left)
    and same(p.right, q.right)
```

This checks structure and values at the same time.

## Algorithm

Define a recursive function:

```python
isSameTree(p, q)
```

At each call:

1. If both nodes are `None`, return `True`.
2. If exactly one node is `None`, return `False`.
3. If the values differ, return `False`.
4. Recursively compare the left children.
5. Recursively compare the right children.
6. Return `True` only if both subtree comparisons are true.

## Walkthrough

Use:

```python
p = [1, 2, 3]
q = [1, 2, 3]
```

Compare roots:

```python
p.val = 1
q.val = 1
```

They match.

Compare left children:

```python
p.left.val = 2
q.left.val = 2
```

They match.

Their children are all `None`, so those empty subtrees match.

Compare right children:

```python
p.right.val = 3
q.right.val = 3
```

They match.

Their children are also `None`.

Every corresponding position matches, so return:

```python
True
```

Now use:

```python
p = [1, 2]
q = [1, None, 2]
```

Compare roots:

```python
1 == 1
```

The roots match.

Compare left children:

```python
p.left exists
q.left is None
```

One side has a node and the other side does not.

Return:

```python
False
```

## Correctness

The algorithm compares the two trees at corresponding positions.

If both nodes are `None`, then both trees are empty at that position, so that position is identical.

If exactly one node is `None`, then one tree has a node where the other does not, so the structures differ and the trees cannot be the same.

If both nodes exist, the algorithm first checks their values. If the values differ, the trees cannot be the same. If the values match, the trees are the same at this position only if their left subtrees are the same and their right subtrees are the same.

This is exactly the recursive definition of identical binary trees.

Therefore, the algorithm returns `True` exactly when the two trees have the same structure and the same values at every corresponding node.

## Complexity

Let:

```python
n = number of nodes compared
h = maximum height of the two trees
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each corresponding node pair is checked at most once |
| Space | `O(h)` | Recursion stack depth follows tree height |

In the worst case, the trees are identical and `n` is the total number of nodes in either tree.

For a skewed tree, `h = n`.

For a balanced tree, `h = O(log n)`.

## Implementation

```python
# 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 isSameTree(
        self,
        p: Optional[TreeNode],
        q: Optional[TreeNode],
    ) -> bool:
        if p is None and q is None:
            return True

        if p is None or q is None:
            return False

        if p.val != q.val:
            return False

        return (
            self.isSameTree(p.left, q.left)
            and self.isSameTree(p.right, q.right)
        )
```

## Code Explanation

First handle the case where both nodes are empty:

```python
if p is None and q is None:
    return True
```

Then handle structural mismatch:

```python
if p is None or q is None:
    return False
```

At this point, both nodes exist.

Compare their values:

```python
if p.val != q.val:
    return False
```

Finally, compare both subtrees:

```python
return (
    self.isSameTree(p.left, q.left)
    and self.isSameTree(p.right, q.right)
)
```

The `and` is important. Both the left and right subtrees must match.

## Iterative BFS Implementation

We can also compare nodes level by level with a queue.

```python
from collections import deque

class Solution:
    def isSameTree(
        self,
        p: Optional[TreeNode],
        q: Optional[TreeNode],
    ) -> bool:
        queue = deque([(p, q)])

        while queue:
            a, b = queue.popleft()

            if a is None and b is None:
                continue

            if a is None or b is None:
                return False

            if a.val != b.val:
                return False

            queue.append((a.left, b.left))
            queue.append((a.right, b.right))

        return True
```

This has the same `O(n)` time complexity.

Its space complexity is `O(w)`, where `w` is the maximum width of the trees.

## Testing

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    p = TreeNode(1, TreeNode(2), TreeNode(3))
    q = TreeNode(1, TreeNode(2), TreeNode(3))
    assert s.isSameTree(p, q) is True

    p = TreeNode(1, TreeNode(2), None)
    q = TreeNode(1, None, TreeNode(2))
    assert s.isSameTree(p, q) is False

    p = TreeNode(1, TreeNode(2), TreeNode(1))
    q = TreeNode(1, TreeNode(1), TreeNode(2))
    assert s.isSameTree(p, q) is False

    assert s.isSameTree(None, None) is True
    assert s.isSameTree(TreeNode(1), None) is False
    assert s.isSameTree(TreeNode(1), TreeNode(1)) is True
    assert s.isSameTree(TreeNode(1), TreeNode(2)) is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3]`, `[1, 2, 3]` | Same structure and values |
| `[1, 2]`, `[1, null, 2]` | Same values, different structure |
| `[1, 2, 1]`, `[1, 1, 2]` | Same structure, different values |
| Two empty trees | Empty trees are the same |
| One empty tree | Structural mismatch |
| Single equal node | Smallest matching non-empty trees |
| Single different node | Value mismatch |