# LeetCode 226: Invert Binary Tree

## Problem Restatement

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

We need to invert the tree and return its root. Inverting means every node swaps its left child and right child.

For example, LeetCode gives this input and output: `root = [4,2,7,1,3,6,9]` becomes `[4,7,2,9,6,3,1]`. The constraints say the tree has between `0` and `100` nodes, and each node value is between `-100` and `100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root node of a binary tree |
| Output | The root of the inverted binary tree |
| Empty tree | Return `None` |
| Operation | Swap the left and right child of every node |

LeetCode gives the usual binary tree node shape:

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

The required function shape is:

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

## Examples

Example 1:

```text
Input:  root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
```

The original tree is:

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

After inversion:

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

Every node swapped its left and right children.

Example 2:

```text
Input:  root = [2,1,3]
Output: [2,3,1]
```

Original:

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

Inverted:

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

Example 3:

```text
Input:  root = []
Output: []
```

An empty tree stays empty.

## First Thought: Traverse Every Node

To invert the whole tree, every node must be visited once.

At each node, we only need one local operation:

```text
swap node.left and node.right
```

The question becomes: how do we visit every node?

A binary tree naturally supports recursive traversal. Each subtree is itself a smaller binary tree.

So the same operation works for:

1. The root.
2. The left subtree.
3. The right subtree.

## Key Insight

To invert a tree rooted at `root`, we can do this:

1. Invert the left subtree.
2. Invert the right subtree.
3. Swap the two inverted subtrees.

The base case is an empty tree.

If `root` is `None`, there is nothing to invert, so we return `None`.

This gives a very small recursive solution.

## Algorithm

For a node `root`:

1. If `root` is `None`, return `None`.
2. Recursively invert `root.left`.
3. Recursively invert `root.right`.
4. Swap `root.left` and `root.right`.
5. Return `root`.

In Python, the swap can be written directly:

```python
root.left, root.right = root.right, root.left
```

Then we continue recursively into the children.

There are two equivalent orders:

```python
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
```

or:

```python
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right
root.right = left
```

Both are correct. The second version makes the recursive structure more explicit, so we will use it.

## Correctness

We prove the algorithm is correct by induction on the size of the tree.

For an empty tree, the algorithm returns `None`. This is correct because the inverse of an empty tree is still empty.

Now consider a non-empty tree with root `root`.

Assume the algorithm correctly inverts the left subtree and the right subtree. This is the induction hypothesis.

The algorithm first computes:

```python
left = self.invertTree(root.left)
right = self.invertTree(root.right)
```

By the induction hypothesis, `left` is the inverted original left subtree, and `right` is the inverted original right subtree.

Then the algorithm assigns:

```python
root.left = right
root.right = left
```

This places the inverted original right subtree on the left side, and the inverted original left subtree on the right side.

That is exactly the definition of a mirrored binary tree.

Therefore, the tree rooted at `root` is correctly inverted. By induction, the algorithm correctly inverts the whole tree.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | The recursion stack has depth equal to the 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 skewed tree, `h = O(n)`.

## Implementation

```python
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None

        left = self.invertTree(root.left)
        right = self.invertTree(root.right)

        root.left = right
        root.right = left

        return root
```

## Code Explanation

The base case handles an empty subtree:

```python
if root is None:
    return None
```

This also handles the case where the whole input tree is empty.

Then we recursively invert both children:

```python
left = self.invertTree(root.left)
right = self.invertTree(root.right)
```

After these calls finish, `left` and `right` already point to inverted subtrees.

Now we swap them:

```python
root.left = right
root.right = left
```

Finally, we return the current root:

```python
return root
```

The root node itself does not change. Only its child pointers change.

## Testing

To test tree problems, it helps to convert between list representation and tree representation.

```python
from collections import deque
from typing import Optional

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

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    q = deque([root])
    i = 1

    while q and i < len(values):
        node = q.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1

    return root

def tree_to_list(root):
    if root is None:
        return []

    result = []
    q = deque([root])

    while q:
        node = q.popleft()

        if node is None:
            result.append(None)
            continue

        result.append(node.val)
        q.append(node.left)
        q.append(node.right)

    while result and result[-1] is None:
        result.pop()

    return result
```

Now we can test the solution:

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

    root = build_tree([4, 2, 7, 1, 3, 6, 9])
    assert tree_to_list(s.invertTree(root)) == [4, 7, 2, 9, 6, 3, 1]

    root = build_tree([2, 1, 3])
    assert tree_to_list(s.invertTree(root)) == [2, 3, 1]

    root = build_tree([])
    assert tree_to_list(s.invertTree(root)) == []

    root = build_tree([1])
    assert tree_to_list(s.invertTree(root)) == [1]

    root = build_tree([1, 2, None, 3])
    assert tree_to_list(s.invertTree(root)) == [1, None, 2, None, 3]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[4,2,7,1,3,6,9]` | Full binary tree |
| `[2,1,3]` | Small normal tree |
| `[]` | Empty tree |
| `[1]` | Single node |
| `[1,2,None,3]` | Skewed tree |