# Binary Tree Level Order Traversal

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

## 1. Core Invariant / The Trick

Standard FIFO BFS queue: snapshot `qLen = len(q)` at the start of every outer loop iteration so the inner loop consumes strictly one depth level.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(W)`
- **Proof**: Every node is enqueued and dequeued once; queue holds at most the widest level W <= N/2.

## 3. Minimal Idiomatic Code

### Python
```python
def levelOrder(root: Optional[TreeNode]) -> list[list[int]]:
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res
```

### TypeScript
```typescript
export function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  let q: TreeNode[] = [root];
  while (q.length > 0) {
    const nextQ: TreeNode[] = [];
    const level: number[] = [];
    for (const node of q) {
      level.push(node.val);
      if (node.left) nextQ.push(node.left);
      if (node.right) nextQ.push(node.right);
    }
    res.push(level);
    q = nextQ;
  }
  return res;
}
```

### C++
```cpp
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q{{root}};
    while (!q.empty()) {
        int n = q.size();
        res.emplace_back();
        while (n--) {
            auto* cur = q.front(); q.pop();
            res.back().push_back(cur->val);
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return res;
}
```

### Java
```java
List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new ArrayDeque<>(List.of(root));
    while (!q.isEmpty()) {
        int n = q.size();
        List<Integer> level = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            TreeNode cur = q.poll();
            level.add(cur.val);
            if (cur.left != null) q.add(cur.left);
            if (cur.right != null) q.add(cur.right);
        }
        res.add(level);
    }
    return res;
}
```

### Go
```go
func levelOrder(root *TreeNode) [][]int {
    if root == nil { return nil }
    var res [][]int
    q := []*TreeNode{root}
    for len(q) > 0 {
        n := len(q)
        level := make([]int, 0, n)
        for i := 0; i < n; i++ {
            cur := q[0]; q = q[1:]
            level = append(level, cur.Val)
            if cur.Left != nil { q = append(q, cur.Left) }
            if cur.Right != nil { q = append(q, cur.Right) }
        }
        res = append(res, level)
    }
    return res
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Reading `len(q)` dynamically inside the inner loop merges multiple levels together.
- Skipping initial `if not root: return []` pushes `None` into the queue.

### Follow-ups
- Binary Tree Right Side View appends only the last element `level[-1]` of each BFS batch.