314. Binary Tree Vertical Order Traversal

314

MediumTrees and Binary Search TreesBFS with column bucketingBFS tagging nodes with a column index

Binary Tree Vertical Order Traversal

Given the root of a binary tree, return its vertical order traversal: group node values by their column (root is column 0, a left child is column-1, a right child is column+1), list columns left to right, and within a column order nodes top to bottom, with ties on the same row kept in left-to-right order.

Open official problem prompt ↗

In plain English

Bucket every node by its horizontal column and output the columns left to right, each read top to bottom.

Picture it like this

Sorting mail into vertical pigeonholes: the column decides which slot, and because you process floor by floor, higher letters land in each slot before lower ones.

Example

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Why: Columns are 9 at -1; 3 and 15 at 0 (3 is higher); 20 at +1; 7 at +2, read left to right.

Constraints

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

Pattern lesson

See the pattern, then code

BFS tagging nodes with a column index

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Assign each node a column offset (parent's column minus one going left, plus one going right) and bucket values by column; a BFS guarantees higher nodes are appended before lower ones, giving the required top-to-bottom order for free.

New words, made simpleKnow these before the algorithm

Column index: A horizontal coordinate: root is 0, left decreases it, right increases it.
BFS (level order): Processing the tree row by row using a queue.
Bucketing: Grouping items into lists keyed by a coordinate.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

DFS with (row, col) then sort

Needs an explicit sort to restore top-to-bottom order because DFS visits out of row order.

Collect all (col, row, val) triples with DFS and sort them.

Time O(n log n)Space O(n)

Best choiceBFS carrying columns

No sorting needed; BFS order already gives top-to-bottom, left-to-right.

Level-order sweep appends values into per-column buckets in the correct vertical order.

Time O(n)Space O(n)

The rule we keep true

Invariant

When a node is dequeued, every node above it (smaller row) has already been appended, so each column bucket stays in top-to-bottom order.

Why this is correct

Reasoning

BFS dequeues nodes in nondecreasing row order and, within a row, left to right, which is exactly the tie-breaking rule the problem requires. Bucketing by column and reading min to max column then reproduces the specified output.

The algorithm in three movesSay these aloud before coding

1BFS from the root, storing (node, column) pairs in a queue

col -1: [9]

2Append each node's value into a dictionary keyed by column

col 0: [3,15]

3Track the minimum and maximum column seen

col 1: [20]

4Emit the buckets in order from the min column to the max column

col 2: [7]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

3,151

202

1 · Read(3, col 0)

2 · AskBucket and enqueue children

3 · Update statecols{0:[3]}; queue=[(9,-1),(20,1)]

4 · Resultmin_c=-1, max_c=1 after children

Key takeaway

Columns keyed from -1 to +2; BFS keeps 3 above 15 within column 0.

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
Lines 3-4Empty guard
Return an empty list when there is no tree.
2
Lines 5-7Queue and buckets
Seed BFS with the root at column 0 and track the column range.
3
Lines 8-17Sweep
Dequeue, record the value in its column, and enqueue children with shifted columns.
4
Lines 18Assemble
Read buckets from the smallest to largest column to build the answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty tree returns []
A single node returns [[val]]
A left-skewed tree spreads across increasingly negative columns
Two nodes sharing a column and row keep left-before-right order

Common beginner mistakes

Using DFS without sorting, which mixes up top-to-bottom order inside a column
Sorting each column by value rather than by position (this problem is column 987 with a different rule)
Forgetting to track min/max columns and iterating the dict in insertion order

Check your understanding

Why does BFS avoid the explicit sort that a DFS solution needs?

PyPython 3 · solution.py

Optimal

1class Solution:2    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:3        if not root:4            return []5        cols = collections.defaultdict(list)6        queue = collections.deque([(root, 0)])7        min_c = max_c = 08        while queue:9            node, c = queue.popleft()10            cols[c].append(node.val)11            min_c = min(min_c, c)12            max_c = max(max_c, c)13            if node.left:14                queue.append((node.left, c - 1))15            if node.right:16                queue.append((node.right, c + 1))17        return [cols[c] for c in range(min_c, max_c + 1)]

Time complexityO(n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MetaAmazonMicrosoft

Binary Tree Vertical Order Traversal

Binary Tree Vertical Order Traversal

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees