0758MediumArrayHash TableDivide and ConquerTreeBinary Tree

Rebuilding The Inspection Rig

Tracked in this browser only

Trains the technique from

LeetCode 889Construct Binary Tree from Preorder and Postorder 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 parcel line is built as a binary tree of inspection stations. Every station has a distinct label and at most two downstream stations, one on its left branch and one on its right.

A single parcel is pushed through the whole rig. Two logs come out of that run:

entry_log records a station's label the moment the parcel arrives at it, which happens before the parcel goes down that station's left branch and then its right branch;
exit_log records a station's label once both of its branches have been fully worked, so a station is written only after every station below it.

Rebuild the rig. When the two logs do not pin down which side a lone downstream station sits on, put it on the left: for every station that has at least one downstream station, the label written immediately after it in entry_log is its left branch station.

Return the rebuilt rig as a flat level-order encoding: entry 0 is the root's label, and after that, taking the present stations in level-order, each one contributes the next two entries as its left slot and then its right slot, with null for an absent station. Drop trailing null entries.

Examples

Example 1

Input: entry_log = [3, 5, 1, 2], exit_log = [1, 5, 2, 3]
Output: [3, 5, 2, 1]

Station 3 is the root, station 5 sits on its left branch with station 1 below 5, and station 2 sits on the root's right branch. Running a parcel through that rig writes 3, 5, 1, 2 on arrival and 1, 5, 2, 3 on completion, which is exactly the pair given.

Example 2

Input: entry_log = [4, 1], exit_log = [1, 4]
Output: [4, 1]

Station 4 is the root and station 1 is its only downstream station. The logs do not say which branch it hangs from, and the stated rule puts it on the left.

Example 3

Input: entry_log = [2, 6, 5, 1, 3, 4], exit_log = [5, 1, 6, 4, 3, 2]
Output: [2, 6, 3, 5, 1, 4]

Root 2 has station 6 on its left and station 3 on its right; station 6 has 5 and 1 below it, and station 3 has 4 on its left. Both logs read back off that rig unchanged.

Constraints

1 <= entry_log.length <= 30
exit_log.length == entry_log.length
1 <= entry_log[i] <= 30
1 <= exit_log[i] <= 30
The labels are the integers from 1 to the number of stations, each appearing once in each log.
The two logs are guaranteed to come from one run over a single binary rig.

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 rebuild_station_tree(entry_log: list[int], exit_log: list[int]) -> list:

Java

public Integer[] rebuildStationTree(int[] entryLog, int[] exitLog)

The intended approach

Time O(n) for n stations: each label is pushed and popped at most once.Space O(n) for the stack, the station links and the returned encoding.

Sweep `entry_log` once, keeping an explicit stack of the stations still waiting for downstream slots. Before attaching the next label, close off every station on top of the stack whose label matches the next unconsumed `exit_log` entry, advancing that cursor each time; whatever remains on top is the station the new one belongs to, taking its left slot when free and its right slot otherwise. Finally walk the finished rig tier by tier to emit the encoding.

Pythonentry point: rebuild_station_tree

def rebuild_station_tree(entry_log, exit_log):
    # An explicit stack holds the chain of stations still waiting for children, so
    # depth never touches the interpreter's call stack.
    # Time O(n), space O(n).
    val = [entry_log[0]]
    left = [None]
    right = [None]
    stack = [0]
    done = 0
    for k in range(1, len(entry_log)):
        val.append(entry_log[k])
        left.append(None)
        right.append(None)
        node = len(val) - 1
        while stack and val[stack[-1]] == exit_log[done]:
            stack.pop()
            done += 1
        top = stack[-1]
        if left[top] is None:
            left[top] = node
        else:
            right[top] = node
        stack.append(node)

    out = [val[0]]
    layer = [0]
    while layer:
        nxt = []
        for nd in layer:
            for ch in (left[nd], right[nd]):
                out.append(None if ch is None else val[ch])
                if ch is not None:
                    nxt.append(ch)
        layer = nxt
    while out and out[-1] is None:
        out.pop()
    return out

The obvious version

Split both logs into matching ranges instead. The first `entry_log` label of a range is that subtree's root, the next one roots its left branch, and looking that label up in `exit_log` reveals where the left branch ends, which splits both ranges. Work items are held on an explicit stack, with a lookup table from label to `exit_log` position.

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_rebuild_station_tree(entry_log, exit_log):
    where = {v: i for i, v in enumerate(exit_log)}
    val = []
    left = []
    right = []
    root = None
    work = [(0, len(entry_log) - 1, 0, len(exit_log) - 1, None, 0)]
    while work:
        pl, pr, ql, qr, par, side = work.pop()
        val.append(entry_log[pl])
        left.append(None)
        right.append(None)
        node = len(val) - 1
        if par is None:
            root = node
        elif side == 0:
            left[par] = node
        else:
            right[par] = node
        if pl == pr:
            continue
        idx = where[entry_log[pl + 1]]
        lsize = idx - ql + 1
        work.append((pl + 1, pl + lsize, ql, idx, node, 0))
        if pl + lsize < pr:
            work.append((pl + lsize + 1, pr, idx + 1, qr - 1, node, 1))

    out = [val[root]]
    layer = [root]
    while layer:
        nxt = []
        for nd in layer:
            for ch in (left[nd], right[nd]):
                out.append(None if ch is None else val[ch])
                if ch is not None:
                    nxt.append(ch)
        layer = nxt
    while out and out[-1] is None:
        out.pop()
    return out

How this problem was checked

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