0626EasyStackTreeDepth-First SearchBinary Tree

Fitting Order for a Parts Tree

Tracked in this browser only

Trains the technique from

LeetCode 145Binary Tree 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 workshop builds a machine from nested sub-assemblies. Each unit is stamped with a signed part code, and each unit is fitted out of at most two sub-assemblies, one the fitters call the left one and one they call the right one. No sub-assembly ever contains a unit that already contains it, so the parts branch and never close a loop.

The machine arrives as units, a level-order listing. Its first entry is the part code of the outermost unit. After that, the listing gives the left then right sub-assembly of each unit already listed, in the order those units appear, writing null where a unit has no sub-assembly on that side. Slots below a null are never written down. An empty listing means there is nothing to build.

A unit can only be fitted once both of its sub-assemblies are already fitted, and the left one is always fitted before the right one. Return the part codes in the order the fitters log them.

Examples

Example 1

Input: units = [7, 4, 9, 2, 6]
Output: [2, 6, 4, 9, 7]

Unit 4 holds sub-assemblies 2 and 6, and unit 7 holds 4 on the left and 9 on the right. Logging 2, then 6, then 4, then 9, then 7 has every unit's sub-assemblies already logged before the unit itself, with each left one ahead of its right one.

Example 2

Input: units = [8, null, 6, 4]
Output: [4, 6, 8]

Unit 8 has no left sub-assembly, so its right one, unit 6, is next in the listing. Unit 6 holds only a left sub-assembly, unit 4. The log is 4, then 6, then 8.

Example 3

Input: units = [20, 9, 30, 4, 12, null, 41]
Output: [4, 12, 9, 41, 30, 20]

Unit 9 holds 4 and 12, and unit 30 has no left sub-assembly but holds 41 on the right. Reading the log back, every unit appears after both of the units it holds.

Constraints

The number of units in the machine is in the range [0, 100].
-100 <= units[i] <= 100 for every slot that holds a unit
units is a level-order listing as described, so units[0] is never null when the listing 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 assembly_order(units: list[int | None]) -> list[int]:

Java

public List<Integer> assemblyOrder(Integer[] units)

The intended approach

Time O(n) for n listed slots: the wiring sweep and the logging walk each touch a unit a constant number of times.Space O(n) for the child tables and the stack, plus the returned list.

First turn the listing into two child tables by sweeping it with a queue: pop the next listed unit and claim the next two slots as its left and right sub-assembly, skipping slots that hold null. Then log the codes with an explicit stack whose entries carry a flag saying whether that unit's sub-assemblies have been pushed yet. Meeting a unit for the first time pushes it back with the flag set and then pushes its right and left sub-assemblies on top, so the left one is popped first and the unit itself is only logged once both have come back off the stack.

Pythonentry point: assembly_order

def _wire(units):
    """Return (left, right) child index tables for the compact level-order listing."""
    if not units or units[0] is None:
        return None, None
    below_left = [-1] * len(units)
    below_right = [-1] * len(units)
    queue = [0]
    head = 0
    slot = 1
    while head < len(queue) and slot < len(units):
        here = queue[head]
        head += 1
        if slot < len(units):
            if units[slot] is not None:
                below_left[here] = slot
                queue.append(slot)
            slot += 1
        if slot < len(units):
            if units[slot] is not None:
                below_right[here] = slot
                queue.append(slot)
            slot += 1
    return below_left, below_right

def assembly_order(units):
    # explicit stack, so a listing that is one long chain cannot exhaust the interpreter
    below_left, below_right = _wire(units)
    if below_left is None:
        return []
    order = []
    pending = [(0, False)]
    while pending:
        here, cleared = pending.pop()
        if here == -1:
            continue
        if cleared:
            order.append(units[here])
        else:
            pending.append((here, True))
            pending.append((below_right[here], False))
            pending.append((below_left[here], False))
    return order

The obvious version

Wire the listing up the same way, then recurse: the log for a unit is the log for its left sub-assembly, followed by the log for its right one, followed by the unit's own code. Builds and concatenates a fresh list at every unit, so it is far heavier than the single stack walk, but it reads straight off the rule.

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 _wire(units):
    """Return (left, right) child index tables for the compact level-order listing."""
    if not units or units[0] is None:
        return None, None
    below_left = [-1] * len(units)
    below_right = [-1] * len(units)
    queue = [0]
    head = 0
    slot = 1
    while head < len(queue) and slot < len(units):
        here = queue[head]
        head += 1
        if slot < len(units):
            if units[slot] is not None:
                below_left[here] = slot
                queue.append(slot)
            slot += 1
        if slot < len(units):
            if units[slot] is not None:
                below_right[here] = slot
                queue.append(slot)
            slot += 1
    return below_left, below_right

def bf_assembly_order(units):
    below_left, below_right = _wire(units)
    if below_left is None:
        return []

    def walk(here):
        if here == -1:
            return []
        return walk(below_left[here]) + walk(below_right[here]) + [units[here]]

    return walk(0)

How this problem was checked

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