# LeetCode 102: Binary Tree Level Order Traversal

## Problem Restatement

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

We need to return the node values level by level, from left to right inside each level. The official problem asks for the level order traversal of the binary tree's node values.

For this tree:

```text
        3
      /   \
     9     20
          /  \
         15   7
```

The answer is:

```python
[[3], [9, 20], [15, 7]]
```

Each inner list contains one tree level.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root node of a binary tree |
| Output | A list of lists of integers |
| Order | Top to bottom, left to right inside each level |
| Empty tree | Return `[]` |

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 levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        ...
```

## Examples

Consider this tree:

```text
        3
      /   \
     9     20
          /  \
         15   7
```

Level `0` contains only the root:

```python
[3]
```

Level `1` contains the children of `3`:

```python
[9, 20]
```

Level `2` contains the children of `9` and `20`, from left to right:

```python
[15, 7]
```

So the final answer is:

```python
[[3], [9, 20], [15, 7]]
```

For a single-node tree:

```text
1
```

The answer is:

```python
[[1]]
```

For an empty tree:

```python
[]
```

The answer is:

```python
[]
```

## First Thought: Traverse by Depth

We need all nodes at depth `0`, then all nodes at depth `1`, then all nodes at depth `2`, and so on.

This order suggests breadth-first search.

Depth-first search goes down one path before coming back.

Breadth-first search processes the tree one layer at a time.

A queue is the natural data structure for this because the first node inserted should be the first node processed.

## Key Insight

At any moment, the queue can hold all nodes from the current level.

Before processing a level, record the queue size.

That size tells us exactly how many nodes belong to the current level.

For example, if the queue contains:

```python
[9, 20]
```

then the current level has size `2`.

We process exactly two nodes, collect their values, and append their children to the queue for the next level.

This keeps level boundaries clean.

## Algorithm

If `root` is `None`, return an empty list.

Otherwise:

1. Create a queue and put `root` into it.
2. Create an empty result list.
3. While the queue is not empty:
   1. Read the current queue size.
   2. Create an empty list for this level.
   3. Process exactly that many nodes.
   4. Append each node value to the current level list.
   5. Add the node's left child if it exists.
   6. Add the node's right child if it exists.
   7. Append the level list to the result.
4. Return the result.

## Correctness

The queue starts with the root, so the first processed level is level `0`.

At the start of each loop, the queue contains exactly the nodes of the current level, ordered from left to right.

We store the queue size before adding children. Therefore, the loop processes only nodes from the current level. Children added during this loop belong to the next level, so they wait in the queue until the next outer loop iteration.

For each node, we append the left child before the right child. This preserves left-to-right order for the next level.

By induction over the tree levels, every level is appended to the result in top-to-bottom order, and every node inside each level appears from left to right. Therefore, the algorithm returns the required level order traversal.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is added to and removed from the queue once |
| Space | `O(n)` | The queue may hold many nodes from one level |

Here, `n` is the number of nodes in the tree.

The output itself also stores `n` values.

## Implementation

```python
from collections import deque
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 levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        if root is None:
            return []

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

        while q:
            level = []

            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left is not None:
                    q.append(node.left)

                if node.right is not None:
                    q.append(node.right)

            ans.append(level)

        return ans
```

## Code Explanation

We first handle the empty tree:

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

Then we create the answer list and the queue:

```python
ans = []
q = deque([root])
```

The queue starts with the root because level order traversal begins at the root.

The outer loop runs while there are still nodes to process:

```python
while q:
```

For each level, we create a fresh list:

```python
level = []
```

This loop is the important part:

```python
for _ in range(len(q)):
```

`len(q)` is measured before the loop starts. That gives the number of nodes currently in this level.

Inside the loop, we remove the next node:

```python
node = q.popleft()
```

Then we store its value:

```python
level.append(node.val)
```

After that, we add its children for the next level:

```python
if node.left is not None:
    q.append(node.left)

if node.right is not None:
    q.append(node.right)
```

After all nodes of the current level are processed, we append the level to the answer:

```python
ans.append(level)
```

Finally:

```python
return ans
```

## Testing

```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

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        if root is None:
            return []

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

        while q:
            level = []

            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left is not None:
                    q.append(node.left)

                if node.right is not None:
                    q.append(node.right)

            ans.append(level)

        return ans

def run_tests():
    s = Solution()

    root1 = TreeNode(
        3,
        TreeNode(9),
        TreeNode(20, TreeNode(15), TreeNode(7)),
    )
    assert s.levelOrder(root1) == [[3], [9, 20], [15, 7]]

    root2 = TreeNode(1)
    assert s.levelOrder(root2) == [[1]]

    root3 = None
    assert s.levelOrder(root3) == []

    root4 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), None),
        TreeNode(3, None, TreeNode(5)),
    )
    assert s.levelOrder(root4) == [[1], [2, 3], [4, 5]]

    root5 = TreeNode(
        1,
        TreeNode(2, TreeNode(3, TreeNode(4))),
        None,
    )
    assert s.levelOrder(root5) == [[1], [2], [3], [4]]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[3,9,20,null,null,15,7]` | Standard multi-level tree |
| Single node | Minimum non-empty tree |
| Empty tree | Confirms `[]` result |
| Uneven tree | Confirms left-to-right ordering across gaps |
| Skewed tree | Confirms one-node-per-level traversal |