# LeetCode 101: Symmetric Tree

## Problem Restatement

We are given the `root` of a binary tree.

We need to check whether the tree is symmetric around its center. In other words, the left subtree must be a mirror image of the right subtree. The official problem asks whether the binary tree is a mirror of itself.

A tree like this is symmetric:

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

The left side and right side have the same shape, but reversed.

A tree like this is not symmetric:

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

Both sides contain `3`, but their positions do not mirror each other.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root node of a binary tree |
| Output | `True` if the tree is symmetric, otherwise `False` |
| Node value | Each node stores an integer value |
| Main condition | The left subtree must mirror the right subtree |

LeetCode gives the `TreeNode` class:

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

The function shape is:

```python
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        ...
```

## Examples

Consider this tree:

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

The root value is `1`.

The left child and right child both have value `2`.

Now compare their children as mirrors:

```text
left.left   should match   right.right
left.right  should match   right.left
```

So we compare:

```text
3 with 3
4 with 4
```

Everything matches, so the answer is:

```python
True
```

Now consider this tree:

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

At first, the two `2` nodes match.

But the left subtree has `3` as a right child, while the right subtree also has `3` as a right child.

For symmetry, the right subtree should have `3` as a left child.

So the answer is:

```python
False
```

## First Thought: Compare the Two Sides

A symmetric tree has a simple rule:

The left subtree and the right subtree must be mirror images.

That means we should not compare:

```text
left.left with right.left
left.right with right.right
```

That would check whether both subtrees are identical.

Instead, we compare across the center:

```text
left.left with right.right
left.right with right.left
```

This is the core idea.

## Key Insight

We can define a helper function:

```python
mirror(a, b)
```

This function answers one question:

“Are the two trees rooted at `a` and `b` mirrors of each other?”

For two nodes to be mirrors:

1. Both nodes are missing, so they match.
2. One node is missing and the other exists, so they do not match.
3. Both nodes exist, but their values differ, so they do not match.
4. Both nodes exist with the same value, so their children must mirror across the center.

The recursive mirror check is:

```text
a.left  mirrors b.right
a.right mirrors b.left
```

## Algorithm

Start from the root.

If the tree is empty, return `True`.

Otherwise, compare the root's left child with the root's right child.

For each pair of nodes:

1. If both nodes are `None`, return `True`.
2. If only one node is `None`, return `False`.
3. If the values are different, return `False`.
4. Recursively compare the outside pair.
5. Recursively compare the inside pair.
6. Return `True` only if both recursive checks are true.

## Correctness

The helper function `mirror(a, b)` checks exactly the definition of mirror symmetry.

If both nodes are missing, the two empty subtrees are mirrors.

If one node is missing and the other exists, the shape differs, so the subtrees cannot be mirrors.

If both nodes exist but their values differ, the subtrees cannot be mirrors because matching mirrored positions must contain the same value.

If both nodes exist and have the same value, the remaining condition is structural. The outside children must mirror each other, and the inside children must mirror each other:

```text
a.left  with b.right
a.right with b.left
```

The recursion applies the same rule at every lower level of the tree.

The full tree is symmetric exactly when `root.left` and `root.right` are mirrors. Therefore, the algorithm returns `True` exactly for symmetric trees.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited at most once |
| Space | `O(h)` | The recursion stack depends on tree height |

Here, `n` is the number of nodes and `h` is the height of the tree.

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

For a completely skewed tree, `h = O(n)`.

## Implementation

```python
from typing import Optional

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
            if a is None and b is None:
                return True

            if a is None or b is None:
                return False

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

            return mirror(a.left, b.right) and mirror(a.right, b.left)

        return mirror(root.left, root.right)
```

## Code Explanation

The helper function compares two nodes at mirrored positions:

```python
def mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
```

If both are missing, they match:

```python
if a is None and b is None:
    return True
```

If only one is missing, the shape is different:

```python
if a is None or b is None:
    return False
```

If both exist but have different values, symmetry fails:

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

Then we compare the mirrored children:

```python
return mirror(a.left, b.right) and mirror(a.right, b.left)
```

The outer pair is `a.left` and `b.right`.

The inner pair is `a.right` and `b.left`.

Finally, the whole tree is symmetric when the left and right children of the root mirror each other:

```python
return mirror(root.left, root.right)
```

## Testing

For local testing, we can define a small `TreeNode` class and build trees manually.

```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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
            if a is None and b is None:
                return True

            if a is None or b is None:
                return False

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

            return mirror(a.left, b.right) and mirror(a.right, b.left)

        return mirror(root.left, root.right)

def run_tests():
    s = Solution()

    root1 = TreeNode(
        1,
        TreeNode(2, TreeNode(3), TreeNode(4)),
        TreeNode(2, TreeNode(4), TreeNode(3)),
    )
    assert s.isSymmetric(root1) is True

    root2 = TreeNode(
        1,
        TreeNode(2, None, TreeNode(3)),
        TreeNode(2, None, TreeNode(3)),
    )
    assert s.isSymmetric(root2) is False

    root3 = TreeNode(1)
    assert s.isSymmetric(root3) is True

    root4 = TreeNode(
        1,
        TreeNode(2),
        TreeNode(3),
    )
    assert s.isSymmetric(root4) is False

    root5 = TreeNode(
        1,
        TreeNode(2, TreeNode(3), None),
        TreeNode(2, None, TreeNode(3)),
    )
    assert s.isSymmetric(root5) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Full mirrored tree | Confirms normal symmetric case |
| Same side child placement | Confirms shape must mirror, not merely values |
| Single node | A single root is symmetric |
| Different child values | Confirms value mismatch fails |
| Missing children mirrored correctly | Confirms `None` positions are handled correctly |