Show problems as
Classic problem #987HardHash TableTreeDepth-First SearchBreadth-First SearchSortingBinary Tree

Vertical Order Traversal of a Binary Tree

Real-world version: Notch Readout of a Hanging Mobile
Tracked in this browser only
Read Vertical Order Traversal of a Binary Tree on LeetCode(opens in a new tab)

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

A studio suspends a mobile from one hook. Every piece of the mobile carries a weight and dangles at most two further pieces beneath it, one on a left arm and one on a right arm. An arm carries its piece one notch sideways and one notch further down: a left arm one notch to the left, a right arm one notch to the right. The piece on the hook occupies notch 0 at the top level.

The sculpture reaches you as pieces, a listing that walks the mobile one level at a time from the hook downward and, within a level, from left to right. Slot 0 holds the piece on the hook. Each piece that appears in the listing claims the next two free slots, its left arm first and its right arm second. A slot holding null carries no piece and claims no slots of its own; null slots at the very end of the listing may be dropped.

A photographer wants the mobile written out notch by notch. Produce one group per occupied notch, and place the groups from the leftmost notch to the rightmost. Inside a group, write the weights from the highest piece down to the lowest. Should two pieces of one group hang at the same level, write the lighter weight ahead of the heavier one.

Examples

Example 1

Input
pieces = [12, 5, 40, null, null, 33, 9]
Output
[[5], [12, 33], [40], [9]]

Notch -1 holds only the piece weighing 5. Notch 0 holds the hook piece 12 at the top level and 33 two levels down. Notches 1 and 2 hold 40 and 9.

Example 2

Input
pieces = [4, 7, 7, 2, 6, 1, 3]
Output
[[2], [7], [4, 1, 6], [7], [3]]

Notch 0 collects the hook piece 4 and, two levels down, both 6 and 1. Those two hang at the same level in the same notch, so the lighter 1 is written ahead of 6.

Example 3

Input
pieces = [806]
Output
[[806]]

A single piece hangs on the hook, so one notch is occupied and it holds one weight.

Constraints

  • The number of pieces in the mobile is in the range [1, 1000].
  • 0 <= weight of a piece <= 1000
  • `pieces` is the level-by-level listing described above, so slot 0 always holds a piece.

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 mobile_column_readout(pieces: list[int | None]) -> list[list[int]]:
Java
public List<List<Integer>> mobileColumnReadout(Integer[] pieces)

More on the same topics