# Maximum Depth of Binary Tree

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

## 1. Core Invariant / The Trick

Post-order recurrence: an empty tree has depth `0`; otherwise `1 + max(maxDepth(left), maxDepth(right))`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(H)`
- **Proof**: Every node is visited once in post-order DFS with O(H) call stack depth.

## 3. Minimal Idiomatic Code

### Python
```python
def maxDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))
```

### TypeScript
```typescript
export function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
```

### C++
```cpp
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
```

### Java
```java
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
```

### Go
```go
func maxDepth(root *TreeNode) int {
    if root == nil { return 0 }
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Off-by-one confusion between depth by nodes (root = 1) vs height by edges (root = 0).

### Follow-ups
- Minimum Depth of Binary Tree prefers BFS so the first leaf encountered terminates immediately without scanning deeper subtrees.