← DSA Atlas
Dedicated problem page · #987

Vertical Order Traversal

HardTrees and Binary Search TreesCoordinate labeling then sortDFS with (column, row) coordinates + sorting
Solve on LeetCode ↗
987
HardTrees and Binary Search TreesDFS with (column, row) coordinates + sortingCoordinate labeling then sort

Vertical Order Traversal

Given the root of a binary tree, return its vertical order traversal. Assign the root coordinate (row=0, col=0); a left child is (row+1, col-1) and a right child is (row+1, col+1). Group nodes by column from leftmost to rightmost. Within a column, order nodes from top row to bottom row; when two nodes share the same row and column, order them by ascending value. Return one list of values per column.

Open official problem prompt ↗
In plain English

Produce, for each vertical column of the tree, the list of node values read top-to-bottom, breaking ties within a cell by value.

Picture it like this

Imagine dropping every node straight down onto a number line marked by column index. Nodes landing in the same column form a stack; you read each stack from the highest node down, and if two land at the exact same spot you place the smaller number first.

Example
Input
root = [3,9,20,null,null,15,7]
Output
[[9],[3,15],[20],[7]]
Why
9 sits at col -1; 3 (row 0) and 15 (row 2) share col 0 and are ordered top-down; 20 at col 1; 7 at col 2.
Constraints
The number of nodes is in the range [1, 1000]0 <= Node.val <= 1000
Pattern lesson

See the pattern, then code

Coordinate labeling then sort
Recognition clue

The prompt asks to group tree nodes by a horizontal (column) coordinate with an explicit tie-break rule (row, then value) — a signal to label each node with coordinates and sort, not to rely on traversal order alone.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. If every node carries a (col, row, val) triple, then sorting those triples lexicographically produces exactly the required global order: columns left-to-right, rows top-to-bottom, and equal (col,row) broken by value. Grouping the sorted triples by column then gives the answer.

New words, made simpleKnow these before the algorithm
Column (horizontal distance)
How far left (-) or right (+) a node is from the root; left child decrements, right child increments it.
Row (depth)
The level of the node, increasing by one on each downward step from the root.
Same-cell tie-break
When two nodes share the same (row, column), the smaller value comes first — this is what makes plain BFS insufficient.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
BFS by column with a dict

Fails the tie-break: two nodes in the same row and column can be appended in the wrong order, so their values must still be sorted.

Level-order traverse, appending each value to its column bucket in visit order.

Time O(n log n)Space O(n)
Best choiceLabel every node with (col, row, val) then sort

One global sort encodes all three ordering rules at once — correct and simple.

Collect a triple per node during any traversal, sort all triples lexicographically, and group by column.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

After sorting, the triple list is in exactly the output order: any prefix contains all nodes belonging to columns strictly left of the current one, fully ordered.

Why this is correct

Reasoning

Lexicographic ordering of (col, row, val) matches the problem's precedence exactly: column dominates (left to right), row is the secondary key (top to bottom), and value is the final tie-break for identical positions. Grouping the already-sorted triples by their first component therefore yields each column's list in correct internal order.

The algorithm in three movesSay these aloud before coding
1DFS the tree, recording (col, row, val) for every node with root at (0,0)

triples sorted: (-1,1,9),(0,0,3),(0,2,15),(1,1,20),(2,2,7)

2Sort all triples by col, then row, then value

col -1 -> [9]; col 0 -> [3,15]

3Group consecutive triples that share a column

result = [[9],[3,15],[20],[7]]

4Emit one value list per column in increasing column order

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
3(0,0)0
9(1,-1)1
20(1,1)2
15(2,0)3
7(2,2)4
1 · Readnode 3 at (row 0, col 0)
2 · AskWhat coordinate triple to record?
3 · Update statenodes = [(0,0,3)]
4 · ResultRecurse left with col-1, right with col+1
Key takeaway

Each node labeled with (row, col); nodes 3 and 15 collide in column 0 and are stacked top-to-bottom.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 17-22DFS collecting coordinates

    Each recursive call passes the child's row and column, so every node is stamped with its exact (col, row) position.

  2. 2
    Lines 24Single global sort

    Sorting the (col,row,val) tuples applies all three ordering rules simultaneously.

  3. 3
    Lines 25-28Group and emit

    Iterating the sorted list appends values into per-column buckets that are already in top-down, value-tie-broken order; emitting columns in sorted key order finishes the answer.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single-node tree returns [[root.val]]
  • A left-leaning chain places every node in a distinct decreasing column
  • Multiple nodes sharing the same (row, col) must be value-sorted — the crux of the problem
  • Duplicate values in the same cell are fine; ties are stable under value sort
!

Common beginner mistakes

  • Relying on BFS insertion order and forgetting the same-cell value tie-break
  • Sorting only within a column by row but not by value on ties
  • Mixing up the sign convention (left is col-1, right is col+1)
  • Forgetting that columns can be negative, so you must sort the column keys rather than assume they start at 0
Check your understanding

Why is a plain BFS that appends values per column in visit order not enough here?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split