# Invert Binary Tree

- **Canonical ID**: `invert-binary-tree`
- **Canonical URL**: https://dsacheatsheet.com/problems/invert-binary-tree
- **Difficulty**: easy
- **Patterns**: Trees
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/invert-binary-tree/

## 1. Core Invariant / The Trick

At every node, swap `left` and `right` children, then recursively invert both subtrees (pre-order, post-order, or BFS queue all preserve the mirror invariant).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(H)`
- **Proof**: Visits every tree node once; recursion stack depth equals tree height H (O(log N) balanced, O(N) skewed).

## 3. Minimal Idiomatic Code

### Python
```python
def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root
```

### TypeScript
```typescript
export function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  const tmp = invertTree(root.left);
  root.left = invertTree(root.right);
  root.right = tmp;
  return root;
}
```

### C++
```cpp
TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}
```

### Java
```java
TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = invertTree(root.left);
    root.left = invertTree(root.right);
    root.right = tmp;
    return root;
}
```

### Go
```go
func invertTree(root *TreeNode) *TreeNode {
    if root == nil { return nil }
    root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
    return root
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Sequentially writing `root.left = invert(root.right); root.right = invert(root.left);` mutates `root.left` before the second line reads it unless assigned simultaneously or via temps.

### Follow-ups
- Iterative BFS queue avoids recursion stack overflow on extremely skewed trees of depth 10^5.