# The Level Inspector

> Each floor of the tower tells a different story.

Canonical URL: <https://datadriven.io/problems/the_level_inspector>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given the root of a binary tree (nested dict with 'val', 'left', 'right'; subtrees are dicts or None), return a list where position i is the list of values at depth i (root = depth 0), in left-to-right order.

## Worked solution and explanation

### Why this problem exists in real interviews

This probes **BFS traversal** and the ability to organize tree data by depth. Interviewers use it to check whether candidates understand queue-based level-order traversal versus recursive DFS, and whether they can group nodes correctly without mixing levels.

---

### Break down the requirements

#### Step 1: Use a queue seeded with the root

BFS naturally processes one level at a time. Starting the queue with the root node sets up the first level.

#### Step 2: Process one full level per outer iteration

Snapshot the current queue length at the start of each iteration. That count tells you exactly how many nodes belong to the current depth.

#### Step 3: Collect values left to right

As you dequeue each node from the front, append its value to the current level list. Enqueue its children for the next round.

#### Step 4: Append completed level to the result

Once all nodes at the current depth are processed, push the level list into the result and move on.

---

### The solution

**BFS with queue snapshot per level**

```python
from collections import deque
def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_values = []
        for _ in range(level_size):
            node = queue.popleft()
            level_values.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_values)
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the number of nodes. Every node is enqueued and dequeued exactly once.
> 
> **Space:** O(w) where w is the maximum width of the tree. The queue holds at most one full level at a time.

> **Interviewers Watch For**
>
> Can you explain why snapshotting `len(queue)` at the start of each iteration correctly isolates one level? Candidates who skip this step and try ad-hoc depth tracking often produce bugs on unbalanced trees.

> **Common Pitfall**
>
> Forgetting to handle `None` root. If the tree is empty, returning an empty list immediately avoids an error when trying to enqueue `None`.

---

## Common follow-up questions

- How would you return level order in reverse (bottom to top)? _(Tests whether you can simply reverse the result list or use a stack.)_
- What if you needed the zigzag (alternating left-right, right-left) order? _(Tests deque manipulation or reversing alternate levels.)_
- How would you find the level with the maximum sum? _(Tests combining BFS traversal with aggregation logic.)_
- What changes if the tree is an n-ary tree instead of binary? _(Tests generalization: iterate over all children instead of just left/right.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_level_inspector)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.