0455EasyStackTreeDepth-First SearchBinary Tree

Survey Order Of A Ventilation Split

Tracked in this browser only

Trains the technique from

LeetCode 144Binary Tree Preorder Traversal

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 mine's air supply runs from a single head junction. Every junction sends air on through at most two drifts, one off its left wall and one off its right wall, and each junction carries a signed airflow reading.

Because the harness takes plain JSON, the network arrives as the array junctions, written out depth by depth. junctions[0] is the reading at the head junction. The entries after it come in pairs, giving the left-wall drift and then the right-wall drift of each junction already written out, taken in the same order those junctions were written. A wall with no drift is written null, and a null never claims a pair of its own. Trailing null entries are left off the end, and an empty array means the network was never dug.

A surveyor walks the network like this: on arriving at a junction they write down its reading, then they walk everything hanging off its left wall, and only once that is finished do they walk everything hanging off its right wall.

Return the readings in the order the surveyor writes them down, or an empty list if the network was never dug.

Examples

Example 1

Input: junctions = [42, -8, 17, null, 5, 61]
Output: [42, -8, 5, 17, 61]

The head junction reads 42. Its left-wall drift leads to -8, which has no left drift and a right drift to 5. Once that side is finished the walk crosses to 17 and then to 61.

Example 2

Input: junctions = [90]
Output: [90]

The network is a single junction, so the surveyor writes one reading.

Example 3

Input: junctions = [-3, 26, null, null, 74, 12, -55]
Output: [-3, 26, 74, 12, -55]

The head junction reads -3 and its left wall leads to 26. That junction has nothing off its left wall, and its right wall leads to 74, whose two drifts read 12 and -55.

Constraints

0 <= number of junctions <= 100
-100 <= airflow reading <= 100
0 <= junctions.length <= 201
Every entry of junctions is either null or an integer reading
junctions[0] is a reading whenever junctions is non-empty

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 survey_order(junctions: list) -> list[int]:

Java

public List<Integer> surveyOrder(Integer[] junctions)

The intended approach

Time O(n) for n junctions: each listing entry is read once and each junction is pushed and popped once.Space O(n) for the rebuilt network, the stack and the returned list.

Read the listing once to rebuild each junction's drifts, which works because the pairs arrive in the same order the junctions were listed. Then hold the junctions still owed a visit on an explicit stack, popping one to record its reading and pushing its drifts back so the left wall comes off the stack before the right. The explicit stack keeps a network that is one long drift from touching the interpreter's call depth.

Pythonentry point: survey_order

def survey_order(junctions):
    if not junctions or junctions[0] is None:
        return []
    # Rebuild the network from the listing: the two branches of every junction
    # already listed follow in the same order those junctions were listed.
    readings = [junctions[0]]
    branches = [[]]
    listed = 0
    at = 1
    while listed < len(readings) and at < len(junctions):
        for _ in range(2):
            if at >= len(junctions):
                break
            entry = junctions[at]
            at += 1
            if entry is not None:
                readings.append(entry)
                branches.append([])
                branches[listed].append(len(readings) - 1)
        listed += 1
    # Walk it from an explicit stack, so a network that is one long drift cannot
    # overflow the interpreter's own call depth.
    out = []
    stack = [0]
    while stack:
        node = stack.pop()
        out.append(readings[node])
        for kid in reversed(branches[node]):
            stack.append(kid)
    return out

The obvious version

Rebuild the network keeping the left and right drift of each junction apart, sweep it depth by depth to label every junction with the string of L and R turns that reaches it, then sort those labels as text and read the readings off in that order. O(n * h log n) for depth h.

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_survey_order(junctions):
    if not junctions or junctions[0] is None:
        return []
    readings = [junctions[0]]
    left = [-1]
    right = [-1]
    listed = 0
    at = 1
    while listed < len(readings) and at < len(junctions):
        for slot in range(2):
            if at >= len(junctions):
                break
            entry = junctions[at]
            at += 1
            if entry is not None:
                readings.append(entry)
                left.append(-1)
                right.append(-1)
                idx = len(readings) - 1
                if slot == 0:
                    left[listed] = idx
                else:
                    right[listed] = idx
        listed += 1
    labelled = []
    queue = [(0, "")]
    head = 0
    while head < len(queue):
        node, path = queue[head]
        head += 1
        labelled.append((path, readings[node]))
        if left[node] != -1:
            queue.append((left[node], path + "L"))
        if right[node] != -1:
            queue.append((right[node], path + "R"))
    labelled.sort(key=lambda pair: pair[0])
    return [reading for _, reading in labelled]

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 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