0158EasyStackTreeDepth-First SearchBinary Tree

Manifold Valve Readout

Tracked in this browser only

Trains the technique from

LeetCode 94Binary Tree Inorder 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 test rig pushes fluid through a branching manifold. Every valve carries a stamped tag and has two outlets, a near tap and a far tap, each of which either feeds another valve or is capped.

The manifold reaches you flattened into the list manifold, written one rank at a time from the top valve downward and left to right inside a rank. Each valve that appears claims the next two entries of the list as its near tap and its far tap, in that order, where null marks a capped tap. A capped tap claims no entries of its own. Trailing entries that would record nothing but caps are left off, and an empty list means the rig holds no valves.

A technician always reads the rig in the same order: everything fed by a valve's near tap, then that valve's own tag, then everything fed by its far tap. Return the tags in the order the technician reads them. Tags may repeat, and a rig with no valves reads as an empty list.

Examples

Example 1

Input: manifold = [2, 9, 1, -7, 4, null, -3]
Output: [-7, 9, 4, 2, 1, -3]

Valve 9 feeds -7 on its near tap and 4 on its far tap, so that whole branch reads -7, 9, 4 before the top valve 2. Valve 1 has a capped near tap, so it is read before -3.

Example 2

Input: manifold = [3, 2, null, 1]
Output: [1, 2, 3]

Each valve only feeds a near tap, so the deepest valve is read first and the top valve last.

Example 3

Input: manifold = [5, 5, 5]
Output: [5, 5, 5]

Repeated tags are reported once per valve, so the readout keeps all three.

Constraints

The rig holds between 0 and 100 valves
-100 <= tag of a valve <= 100
manifold entries are integers or null, and the list encodes one real manifold as described

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 valve_readout(manifold: list) -> list[int]:

Java

public List<Integer> valveReadout(Integer[] manifold)

The intended approach

Time O(n), each valve is pushed and popped onceSpace O(n) for the rebuilt rig, plus a stack that grows to the depth of the manifold

Rebuild the valves from the flattened rank listing with one queue, handing each valve the next two entries as its taps. Then walk the rig with a stack instead of recursion: dive down near taps pushing every valve you pass, and when you can go no further, pop a valve, record its tag and step onto its far tap. That is exactly the near-self-far order, and no valve is recorded twice because a valve is only popped after its whole near side is done.

Pythonentry point: valve_readout

def valve_readout(manifold):
    # rebuild: O(n) time, O(n) space
    if not manifold or manifold[0] is None:
        return []
    root = [manifold[0], None, None]
    queue = [root]
    head = 0
    i = 1
    while head < len(queue) and i < len(manifold):
        node = queue[head]
        head += 1
        if i < len(manifold):
            tag = manifold[i]
            i += 1
            if tag is not None:
                node[1] = [tag, None, None]
                queue.append(node[1])
        if i < len(manifold):
            tag = manifold[i]
            i += 1
            if tag is not None:
                node[2] = [tag, None, None]
                queue.append(node[2])
    # readout: O(n) time, O(depth) extra space for the stack
    out = []
    stack = []
    node = root
    while node is not None or stack:
        while node is not None:
            stack.append(node)
            node = node[1]
        node = stack.pop()
        out.append(node[0])
        node = node[2]
    return out

The obvious version

Builds no valve objects at all. Records which list position feeds which tap in two lookup tables, then reads the rig with a recursive function that glues together the near list, the tag and the far list.

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_valve_readout(manifold):
    if not manifold or manifold[0] is None:
        return []
    tags = {0: manifold[0]}
    near = {}
    far = {}
    cursor = 1
    frontier = [0]
    while frontier and cursor < len(manifold):
        nxt = []
        for p in frontier:
            for slot in (1, 2):
                if cursor >= len(manifold):
                    break
                tag = manifold[cursor]
                pos = cursor
                cursor += 1
                if tag is not None:
                    tags[pos] = tag
                    if slot == 1:
                        near[p] = pos
                    else:
                        far[p] = pos
                    nxt.append(pos)
        frontier = nxt

    def walk(p):
        if p is None:
            return []
        return walk(near.get(p)) + [tags[p]] + walk(far.get(p))

    return walk(0)

How this problem was checked

Reference solution executed against 10 test cases — 10 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