Show problems as
Classic problem #145EasyStackTreeDepth-First SearchBinary Tree

Binary Tree Postorder Traversal

Real-world version: Fitting Order for a Parts Tree
Tracked in this browser only
Read Binary Tree Postorder Traversal on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstTraversal · Binary Trees & BST, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def assembly_order(units: list[int | None]) -> list[int]:
Java
public List<Integer> assemblyOrder(Integer[] units)

More on the same topics