Show problems as
Classic problem #314MediumHash TableTreeDepth-First SearchBreadth-First SearchSortingBinary Tree

Binary Tree Vertical Order Traversal

Real-world version: Wall Panel Columns
Tracked in this browser only
Read Binary Tree Vertical Order Traversal on LeetCode(opens in a new tab)

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

A control wall holds labelled junction panels hung in a binary arrangement. The topmost panel occupies column 0. Every panel may carry a lower-left panel and a lower-right panel: the lower-left one hangs one tier down and one column to the left, the lower-right one hangs one tier down and one column to the right.

The wall arrives as panels, a tier-by-tier listing. panels[0] is the top panel's label. The rest of the list is consumed two entries at a time, taking panels in the order they were listed: the next two entries are that panel's lower-left and lower-right labels, where null means no panel hangs there (and therefore contributes no entries of its own). Trailing nulls are omitted, and an empty list means the wall is bare.

Return the labels grouped by column, with the columns ordered from the leftmost to the rightmost. Inside a column, list the labels from the highest tier downwards, and when two panels share both a column and a tier, list the one hanging further left first.

Examples

Example 1

Input
panels = [7, 4, 9]
Output
[[4], [7], [9]]

Panel 4 hangs in column -1, panel 7 in column 0 and panel 9 in column 1.

Example 2

Input
panels = [9, 4, 7, null, 6, null, null, null, 2]
Output
[[4], [9, 6], [7, 2]]

Column -1 holds only panel 4. Column 0 holds panel 9 on tier 0 and panel 6 on tier 2. Column 1 holds panel 7 on tier 1 and panel 2 on tier 3.

Example 3

Input
panels = [1, 2, 3, null, 4, 5]
Output
[[2], [1, 4, 5], [3]]

Panels 4 and 5 both land in column 0 on tier 2, and 4 hangs further left, so it is listed first.

Example 4

Input
panels = []
Output
[]

The wall is bare, so there are no columns to report.

Constraints

  • The number of panels on the wall is in the range [0, 100].
  • -100 <= panel label <= 100

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 vertical_order(panels: list) -> list[list[int]]:
Java
public List<List<Integer>> verticalOrder(Integer[] panels)

More on the same topics