# The Level Summer

> Add up each level of the tree.

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

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

Given a tree rooted at a dict {'val', 'children': [...]}, return a list where position i is the sum of all node vals at depth i (root is depth 0).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **tree traversal with depth tracking** and the ability to aggregate values at each level. It reveals whether a candidate can adapt BFS or DFS to accumulate per-level metrics on a generic tree structure (not just binary trees).

---

### Break down the requirements

#### Step 1: Initialize with BFS from the root

Use a queue that pairs each node with its depth. The root starts at depth 0.

#### Step 2: Accumulate sums per depth

Maintain a list where index i holds the running sum for depth i. Extend the list when encountering a new depth for the first time.

#### Step 3: Enqueue all children with incremented depth

For each node, push every child into the queue with `depth + 1`. This handles arbitrary branching factors.

---

### The solution

**BFS with depth-indexed accumulation**

```python
from collections import deque
def level_sums(root):
    if not root:
        return []
    sums = []
    queue = deque()
    queue.append((root, 0))
    while queue:
        node, depth = queue.popleft()
        if depth == len(sums):
            sums.append(0)
        sums[depth] += node['val']
        for child in node['children']:
            queue.append((child, depth + 1))
    return sums
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the total number of nodes. Each node is visited exactly once.
> 
> **Space:** O(w) for the queue where w is the maximum width, plus O(d) for the sums list where d is the tree depth.

> **Interviewers Watch For**
>
> Do you handle the dict-based tree representation cleanly? Using `node['children']` directly shows comfort with Python dictionary access patterns common in real API responses.

> **Common Pitfall**
>
> Using recursion without a depth parameter. DFS works but you must pass the current depth explicitly. Forgetting to do so produces a flat sum instead of per-level sums.

---

## Common follow-up questions

- How would you find the depth with the maximum sum? _(Tests combining traversal with a max-tracking variable.)_
- What if the tree could have millions of nodes? _(Tests awareness of BFS memory usage and whether iterative deepening DFS would help.)_
- How would you compute level averages instead of sums? _(Tests tracking both sum and count per level.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_level_summer)
- [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.