Depth-first search + parent links

Find the Deepest Storage Route

Original & variant

This variant uses a multi-child directory and returns the deepest named route rather than a depth number.

01. The question

A storage directory has named nodes with any number of children. Return the names along a root-to-leaf route with the most nodes. For tied depths, choose the first route in left-to-right child order. Return [] for an empty directory.

Before revealing the idea, predict the result and describe what information you would need to track.

02. Worked example

InputDepot → [A → [A1, A2], B, C → [C1]]

Output["Depot", "A", "A1"]

Visit Depot, then A, then A1 using a last-in-first-out stack.
A1 sets the best depth to 2. A2 and C1 tie, so neither replaces it.
Follow A1 → A → Depot through parent links, then reverse that list.

Try your code

Your Python solution

Define solve(data, parameter="") and return your result. Your code runs locally, not on a server.

Edit your test cases

Custom test cases (JSON)

Use 1-10 objects with data and an optional string parameter. Expected outputs are computed from the lesson. An optional expected field must be correct.

Input contract & reference code

Example data: {"name":"Depot","children":[{"name":"A","children":[{"name":"A1","children":[]},{"name":"A2","children":[]}]},{"name":"B","children":[]},{"name":"C","children":[{"name":"C1","children":[]}]}]}. Parameter: "". Numeric parameters arrive as strings; convert them with int(parameter) when needed.

The example and generated cases use the question’s exact variant. This checks behavior on a small test batch—not performance on every possible input.

Python runtime notices

Python downloads only when you run code, using compressed runtime assets. Code is not saved or uploaded. Enable JavaScript to run it.

Printed output

Five-second execution limit per batch. Standard-library Python only; additional packages and network access are unavailable. Stop ends execution without blocking the lesson.

03. The idea

Try sketching your own approach first. What would you track, and why would it work?

Reveal the idea

Push children in reverse order so the first child is visited first.
Remember each visited node's parent and depth. Replace the deepest node only for a strictly greater depth.
After the traversal, reconstruct one route using parent links.

04. Watch it happen

Use Step to move slowly, or Play to follow the whole trace. Change a preset or load your own input.

Input & settings

TrySpeedPage style

Red = current item / blue = active window or cells / green = completed work. A value docks at its actual destination; the original input stays unchanged. Positions start at 0.

Working state / what changes

Ready to begin

Enable JavaScript to step through the animation. The worked example and solution below remain readable without it.

Python / why it changes

The line behind the step

def deepest_route(root):
    if root is None:
        return []
    stack = [(root, 0, None)]
    parents = {}
    best_name, best_depth = root["name"], -1
    while stack:
        node, depth, parent = stack.pop()
        name = node["name"]
        parents[name] = parent
        if depth > best_depth:
            best_name, best_depth = name, depth
        for child in reversed(node["children"]):
            stack.append((child, depth + 1, name))
    path = []
    while best_name is not None:
        path.append(best_name)
        best_name = parents[best_name]
    return path[::-1]

How to use this walkthrough

Hover or focus a control for its label. Play forms the input and follows values into the working state. Step shows one change; Back and the slider restore exact snapshots. Reduced motion uses instant updates. Saved snapshots and sorted heap displays are teaching overhead, not algorithm complexity.

05. Python solution

def deepest_route(root):
    if root is None:
        return []
    stack = [(root, 0, None)]
    parents = {}
    best_name, best_depth = root["name"], -1
    while stack:
        node, depth, parent = stack.pop()
        name = node["name"]
        parents[name] = parent
        if depth > best_depth:
            best_name, best_depth = name, depth
        for child in reversed(node["children"]):
            stack.append((child, depth + 1, name))
    path = []
    while best_name is not None:
        path.append(best_name)
        best_name = parents[best_name]
    return path[::-1]

06. Cost & edge cases

Time: O(n)
Space: O(n) for parent links and pending nodes

A single node returns its name in a one-element list.
Names must be unique, so parent lookup is unambiguous.
A deepest node must be a leaf; reversing children preserves the required tie order.

Keep going

Browse all questions Back to Trees & traversal Scan the Warehouse Shelves Plan a Quiet Delivery Measure Connected Garden Plots Follow a Letter-Tile Route