The Level Inspector

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
L4
Asked in
Rackspace Technology

Problem

You're handed a binary tree decoded from a nested-dict export: each node is a dict with an int val plus left and right children that are either another such node or None. Group the values by depth, returning a list whose entry at index i holds every value at depth i in left-to-right order, with the root sitting at depth 0. An empty tree, where root is None, comes back as an empty list.

Each floor of the tower tells a different story.

Example 1

Input:

root = {"val":3,"left":{"val":9,"left":null,"right":null},"right":{"val":20,"left":{"val":15,"left":null,"right":null},"right":{"val":7,"left":null,"right":null}}}

Output:

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

Example 2

Input:

root = null

Output:

[]

Worked solution and explanation

What this really is

Strip the costume and this is level-order traversal with the levels kept apart. Almost anyone can walk a tree breadth-first. What separates candidates is keeping each depth in its own bucket. The move that does it is to snapshot the queue length at the top of each round, because that count is exactly how many nodes sit at the current depth before you start adding their children. Miss that snapshot and your level boundaries dissolve the instant you enqueue the next row. The second trap is quieter: this tree arrives as nested dicts, so node.val throws AttributeError. It is node['val'].

Break down the requirements

Step 1: Understand the nested-dict node shape

Each node is a dict shaped {'val': int, 'left': node_or_None, 'right': node_or_None}. Read a node's value with node['val'] and reach its children with node['left'] and node['right'], where a missing child is None. Guard the empty tree: if root is None, return [] immediately so you never enqueue None.

Step 2: Use a queue seeded with the root

BFS naturally processes one level at a time. Seed the queue with the root dict to set up the first level.

Step 3: 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 before any children get added.

Step 4: Collect values left to right

As you dequeue each node-dict from the front, append node['val'] to the current level list. Then enqueue any non-None node['left'] and node['right'] for the next round.

Step 5: 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
from collections import deque

def level_order_by_level(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"] is not None:
                queue.append(node["left"])
            if node["right"] is not None:
                queue.append(node["right"])
        result.append(level_values)
    return result

Common follow-up questions