Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, return its vertical order traversal.

Assign each node a position (row, col): the root is (0, 0), and a node at (row, col) has its left child at (row + 1, col - 1) and its right child at (row + 1, col + 1). Group nodes by column from left to right. Within a column, order nodes by row (top to bottom); if two nodes share the same row and column, order them by value (smaller first).

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Assign each node a (row, col): left child (row+1, col-1), right child (row+1, col+1).

Group by column (left to right); within a column order by row.

When two nodes share the same (row, col), break the tie by value — the subtle rule here.

Common doubts

Vertical order keeps every node in a column (not just one), and it sorts same-position nodes by value.

Two nodes at the same (row, col) must be ordered by value regardless of when they're visited, so an explicit value sort is required.

The sort by (col, row, value): O(n log n).

Interview follow-ups

· What an interviewer asks next.

It omits the value tie-break, ordering same-column nodes purely by traversal/level order.

Skip the final left-to-right flattening and return the column-to-values map directly.

Fun facts

The value tie-break was added in LeetCode 987 to disambiguate 314's under-specified ordering.
Column index is the same 'horizontal distance' used by top and bottom views.

Asked at

AmazonFacebookMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[9], [3, 15], [20], [7]]
Columns -1, 0, 1, 2. Column 0 holds 3 (row 0) then 15 (row 2).

Example 2

Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [[4], [2], [1, 5, 6], [3], [7]]
In column 0, nodes 5 and 6 share row 2, so they are ordered by value: 5 then 6.

Constraints

- The number of nodes is in the range [0, 1000] - 0 <= Node.val <= 1000

Each node gets a (row, col) coordinate — left decrements the column, right increments it, and both increase the row. The output groups nodes by column (left to right), and inside a column sorts by row, breaking ties by value. So: record (col, row, value) for every node and sort — the tie-break on value is the detail that trips people up.

Prerequisites

Before you start

· Concepts used directly in the solution.

Row/column coordinates. Left child (row+1, col-1); right child (row+1, col+1).

Multi-key sort. Order by column, then row, then value.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Ordering

“How are same-position nodes ordered?”

Two nodes at the same (row, col) are ordered by value, smaller first.

“Column order?”

Left to right, i.e. most negative column first.

The ideal opening — say it like this

Each node has a (row, col); I collect (col, row, value) triples for all nodes.

Sorting by column, then row, then value and grouping by column gives the answer — the value tie-break is the subtle part.

Understand the problem

Worked example — tree [3, 9, 20, null, null, 15, 7]

col -1: 9        col 0: 3, 15     col 1: 20     col 2: 7
(15 and 3 share col 0 but different rows: 3 at row 0, 15 at row 2)
result: [[9], [3, 15], [20], [7]]

Key observations

1Aha

Coordinates drive the grouping

Column groups the output; row orders within a column.

2Aha

Value breaks position ties

Two nodes at the same (row, col) are ordered by value — the rule that makes this harder than the views.

3Aha

Sorting is the workhorse

Collect (col, row, value) triples and sort by all three keys; O(n log n).

Brute force vs optimal

	DFS collect + global sort	BFS + per-column sort
Idea	One sort of all (col,row,val) triples	Bucket by col, sort each by (row,val)
Time	O(n log n)	O(n log n)
Space	O(n)	O(n)

Both sort on the same keys; grouping order is identical. Full code is in the Approaches selector below.

Summary

Key takeaway

Assign (row, col) coordinates, record (col, row, value) per node, and sort by column then row then value. Group by column. O(n log n) — the value tie-break is the crux.

dfs(node, row, col): record (col, row, val); recurse (row+1, col-1) and (row+1, col+1)
sort triples by (col, row, val); group by col