The Level Summer

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L3
Asked in
Ancestry

Problem

Return the combined val of every node at each depth of our category tree, one entry per depth starting from the root, where every node carries an integer val and a list of children that may be empty. We sometimes receive an empty root dict before the tree has loaded, and that should come back as an empty list.

Every tier of the hierarchy keeps its own total.

Example

Input:

root = {"val":1,"children":[{"val":2,"children":[]},{"val":3,"children":[{"val":4,"children":[]},{"val":5,"children":[]}]}]}

Output:

[1,5,9]

Worked solution and explanation

What this really is

Strip the costume and this is a depth-bucketed sum over a ragged tree with any number of children per node. Anyone can walk the tree. The trick is knowing each node's depth the moment you touch it, so its val lands in the right bucket. If you assume the tree is balanced, or index by child position, a shallow leaf sitting beside a deeper subtree lands in the wrong slot, and a tree like the hidden one comes out misaligned instead of [2, 7, 5]. If you forget the empty {} root, root['val'] raises KeyError instead of returning [].

How to get there

Step 1: Carry depth alongside each node

Return [] first when root is the empty dict. Then walk the tree with a queue of (node, depth) pairs, seeded with (root, 0). Pairing the depth with the node means you never have to reconstruct a node's level after the fact, which is exactly where the naive recursive version goes wrong.

Step 2: Grow the buckets lazily

Keep a list where index i is the running total for depth i. The first time you reach a new depth, len(sums) still equals that depth, so append a fresh 0 before adding. That one check means you never index past the end and never need the tree's height in advance, which is what makes ragged trees safe.

Step 3: Enqueue all children, one level deeper

Push every child with depth + 1. Iterating node['children'] directly works for any branching factor, and nodes at the same depth under different parents all fold into the same bucket. Leaves simply add nothing new to the queue.

The solution

BFS with depth-indexed accumulation
from collections import deque

def level_sums(root):
    if not root:
        return []
    sums = []
    queue = deque([(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

The (node, depth) pairing is the load-bearing idea; everything else is bookkeeping.

Depth carried with the node
Each queue entry is (node, depth); the bucket index is known the instant you pop. No second structure, no ambiguity when values repeat across levels.
Depth inferred later
Mapping values back to levels after a flat traversal forces you to track parent pointers or re-walk the tree. Repeated vals make it worse: you cannot tell which level a 1 came from.

Common follow-up questions