# LeetCode 107: Binary Tree Level Order Traversal II

## Problem Restatement

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

We need to return the node values level by level, but from bottom to top. Inside each level, values must still be ordered from left to right.

The official problem asks for the bottom-up level order traversal of the binary tree's node values, from leaf level to root level.

For this tree:

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

Normal level order traversal is:

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

Bottom-up level order traversal is:

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root node of a binary tree |
| Output | A list of lists of integers |
| Level order | Nodes are grouped by depth |
| Inside each level | Values stay left to right |
| Final order | Deepest level first, root level last |
| 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 levelOrderBottom(self, root: Optional[TreeNode]) -> list[list[int]]:
        ...
```

## Examples

Consider this tree:

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

Level `0` contains:

```python
[3]
```

Level `1` contains:

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

Level `2` contains:

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

Normal top-down order is:

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

The problem wants bottom-up order, so we reverse the list of levels:

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

For a single-node tree:

```text
1
```

The answer is:

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

For an empty tree:

```python
root = None
```

The answer is:

```python
[]
```

## First Thought: Use Normal Level Order Traversal

The problem still asks for nodes grouped by level.

That is exactly what breadth-first search gives us.

The only difference from LeetCode 102 is the final order of the levels.

So we can:

1. Run normal BFS from top to bottom.
2. Store each level as a list.
3. Reverse the final answer.

This keeps the traversal simple and makes the bottom-up part explicit.

## Key Insight

We should preserve left-to-right order inside each level.

That means during BFS, we still enqueue children in this order:

```text
left child first
right child second
```

This gives each level in the correct left-to-right order.

After all levels are collected, we reverse only the outer list:

```python
ans.reverse()
```

We do not reverse each inner level.

For example:

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

becomes:

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

The level `[15, 7]` remains left to right.

## Algorithm

If `root` is `None`, return `[]`.

Otherwise:

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

## Correctness

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

At the start of each outer loop, the queue contains exactly the nodes of one level in left-to-right order. We record the queue size before processing that level, so newly added children are not mixed into the current level.

For every processed node, the algorithm adds the left child before the right child. Therefore, the next level is also arranged from left to right in the queue.

Thus, before the final reversal, `ans` contains all levels from root to leaves, with left-to-right order inside each level.

The problem asks for the same levels from leaves to root. Reversing the outer list changes only the order of levels. It does not change the order of values inside each level.

Therefore, the returned list is exactly the required bottom-up level order traversal.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is processed once |
| Space | `O(n)` | The queue and output can store node values |

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

The final reversal costs `O(L)`, where `L` is the number of levels. Since `L <= n`, the total time remains `O(n)`.

## 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 levelOrderBottom(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)

        ans.reverse()
        return ans
```

## Code Explanation

Handle the empty tree first:

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

Create the answer list and queue:

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

The queue lets us process nodes in breadth-first order.

The outer loop processes one level at a time:

```python
while q:
```

For each level, start a new list:

```python
level = []
```

This loop runs exactly once for every node in the current level:

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

Remove the next node and store its value:

```python
node = q.popleft()
level.append(node.val)
```

Add 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 the current level is complete, store it:

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

Finally, reverse the level order:

```python
ans.reverse()
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 levelOrderBottom(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)

        ans.reverse()
        return ans

def run_tests():
    s = Solution()

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

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

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

    root4 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7)),
    )
    assert s.levelOrderBottom(root4) == [[4, 5, 6, 7], [2, 3], [1]]

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

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[3,9,20,null,null,15,7]` | Standard example |
| Single node | Minimum non-empty tree |
| Empty tree | Confirms empty output |
| Complete tree | Confirms each level stays left to right |
| Skewed tree | Confirms bottom-up order with one node per level |