0433EasyStringBacktrackingTreeDepth-First SearchBinary Tree

Cave Routes to Every Dead End

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A caving club has surveyed a dry limestone system. One chamber is the entrance, and every chamber has at most two onward passages leading deeper, one that the surveyors call the left passage and one they call the right. No passage ever rejoins a chamber already visited, so the system branches and never closes a loop. Each chamber is stencilled with its floor height in metres relative to the water table, which may be negative.

The survey reaches you as chambers, listing the system one depth band at a time, left to right. Slot 0 holds the entrance. Every chamber in the listing claims the next two unclaimed slots for its passages, the left one first and the right one second. A slot holding null means no chamber hangs there, and such a slot claims no slots of its own. Trailing null slots may be left off the end of the listing.

A route starts at the entrance, follows onward passages, and finishes at a chamber with no onward passage at all. Write a route as the stencilled heights of the chambers it passes through, entrance first, joined by forward slashes, for example 12/-4/0.

Return every route in the system. The routes may come back in any order.

Examples

Example 1

Input: chambers = [0, -3, 7]
Output: ["0/-3", "0/7"]

The entrance has both passages, and each leads straight to a chamber with nothing beyond it, so there are two routes of two chambers each.

Example 2

Input: chambers = [4, 2, null, 9]
Output: ["4/2/9"]

The entrance has only a left passage, and the chamber it reaches has only a left passage of its own, so the single route runs three chambers deep.

Example 3

Input: chambers = [5]
Output: ["5"]

The entrance is also a dead end, so the one route consists of it alone.

Example 4

Input: chambers = [8, 3, 10, 1, 6, null, 14, null, null, null, 7, 13]
Output: ["8/3/1", "8/3/6/7", "8/10/14/13"]

Three chambers in this system have no onward passage, and each contributes the sequence of heights read from the entrance down to it.

Constraints

The number of surveyed chambers is in the range [1, 100].
-100 <= chambers[i] <= 100 for every slot that holds a chamber
chambers[0] holds a chamber
No slot in the listing follows a slot that holds null and was never claimed

The values you return may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def binary_tree_paths(chambers: list[int | None]) -> list[str]:

Java

public List<String> binaryTreePaths(Integer[] chambers)

The intended approach

Time O(n + L) where n is the listing length and L is the total number of characters in the returned routes: every slot is entered and left once, and a route string is built only at a dead end.Space O(n + L): the two passage tables and the stack are proportional to the listing, the route buffer is bounded by the depth, and the returned routes hold L characters.

Resolve the listing into two tables of slot numbers, one per passage direction, by walking the slots once and handing out the unclaimed slots in order. Then walk the system from an explicit stack that carries an enter marker and a leave marker for each chamber: entering appends the chamber's height to a shared route buffer, leaving strips it back off, and a chamber with neither passage joins the buffer into a finished route string. Driving the walk from a stack rather than nested calls keeps a hundred-deep chain safe.

Pythonentry point: binary_tree_paths

def binary_tree_paths(chambers):
    # One sweep hands every chamber the slot numbers of its two onward passages,
    # honouring the rule that an empty slot claims nothing. A second sweep walks
    # the cave from an explicit stack holding an enter marker and a leave marker
    # per chamber: entering pushes the chamber's mark onto the current route and
    # leaving pops it again, so the route always describes the way back to the
    # entrance. A chamber with no onward passage flushes the route as a string.
    # O(n + L) time and O(n + L) space, where L is the total length of the routes
    # returned; the stack keeps the walk safe on a 100-deep cave.
    size = len(chambers)
    if size == 0 or chambers[0] is None:
        return []
    left = [-1] * size
    right = [-1] * size
    free = 1
    for idx in range(size):
        if chambers[idx] is None:
            continue
        if free < size:
            if chambers[free] is not None:
                left[idx] = free
            free += 1
        if free < size:
            if chambers[free] is not None:
                right[idx] = free
            free += 1

    routes = []
    marks = []
    stack = [(0, False)]
    while stack:
        idx, leaving = stack.pop()
        if leaving:
            marks.pop()
            continue
        marks.append(str(chambers[idx]))
        stack.append((idx, True))
        if left[idx] < 0 and right[idx] < 0:
            routes.append("/".join(marks))
        else:
            if right[idx] >= 0:
                stack.append((right[idx], False))
            if left[idx] >= 0:
                stack.append((left[idx], False))
    return routes

The obvious version

Give every chamber the slot number of the chamber above it and count its onward passages. Then take each chamber that has no onward passage, climb slot by slot up to the entrance collecting heights, reverse what was collected, and join it.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_binary_tree_paths(chambers):
    size = len(chambers)
    if size == 0 or chambers[0] is None:
        return []
    above = [-1] * size
    onward = [0] * size
    free = 1
    for idx in range(size):
        if chambers[idx] is None:
            continue
        for _ in range(2):
            if free < size:
                if chambers[free] is not None:
                    above[free] = idx
                    onward[idx] += 1
                free += 1
    answer = []
    for idx in range(size):
        if chambers[idx] is None or onward[idx] != 0:
            continue
        climb = []
        step = idx
        while step != -1:
            climb.append(str(chambers[step]))
            step = above[step]
        climb.reverse()
        answer.append("/".join(climb))
    return answer

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in