314 - Binary Tree Vertical Order Traversal

Difficulty: Medium | Pattern: BFS + HashMap | Company tags: Facebook, Amazon, Google

Problem Statement

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Example:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Approach: BFS with Column Tracking — O(n log n), O(n)

Key insight: BFS guarantees top-to-bottom, left-to-right order naturally. Track column index for each node. Collect in a HashMap then sort keys.

Note: This differs from LC 987 which also sorts by value within same row/col. Here, BFS order preserves left-to-right naturally.

Algorithm Flow

from collections import defaultdict, deque

def verticalOrder(root) -> list[list[int]]:
    if not root:
        return []
    
    col_map = defaultdict(list)
    queue = deque([(root, 0)])
    min_col = max_col = 0
    
    while queue:
        node, col = queue.popleft()
        col_map[col].append(node.val)
        min_col = min(min_col, col)
        max_col = max(max_col, col)
        
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    
    return [col_map[col] for col in range(min_col, max_col + 1)]

Dry Run

Tree: 3(root), left=9, right=20(left=15,right=7)

BFS order:

node	col	col_map summary
3	0	col0=[3]
9	-1	col-1=[9], col0=[3]
20	1	col-1=[9], col0=[3], col1=[20]
15	0	col-1=[9], col0=[3,15], col1=[20]
7	2	col-1=[9], col0=[3,15], col1=[20], col2=[7]

Result: [[-1→9],[0→3,15],[1→20],[2→7]] = [[9],[3,15],[20],[7]] ✓

LC 987 vs LC 314

	LC 314	LC 987
Same row+col	BFS order (left to right)	Sort by value
Traversal	BFS	DFS or BFS

Complexity

• Time: O(n log n)
• Space: O(n)

Key Terms

Term	Definition
BFS level order	Traversal that visits nodes level by level, guaranteeing top-to-bottom and left-to-right discovery order.
Column index	Integer offset from the root (root = 0), decremented for left children and incremented for right children.
Hash map bucketing by column	Grouping node values into lists keyed by column index, so all nodes sharing a column collect together.
min_col / max_col tracking	Running bounds updated during BFS so the final result can be assembled by iterating columns in order without sorting keys.
Vertical order vs. LC 987	LC 314 preserves BFS (left-to-right) order for ties; LC 987 additionally sorts tied nodes by value.

FAQ

1. Can this be solved without extra space? No — you need at least O(n) space to bucket values by column, since output order depends on grouping across the whole tree, not a single pass.
2. What if the tree is empty? verticalOrder returns [] immediately when root is None, before any BFS starts.
3. How would this change if ties needed to be sorted by value instead of BFS order? That's exactly LC 987 (Vertical Order Traversal II) — sort each column's list by (row, value) instead of relying on BFS insertion order.
4. Why is the complexity O(n log n) if BFS itself is O(n)? Because min_col to max_col range and dict iteration require tracking bounds, and in solutions that use a sorted() over column keys, the sort of at most O(n) distinct columns costs O(n log n) in the worst case. Tracking min_col/max_col during BFS (as this solution does) avoids needing a sort of keys, but interviewers still expect you to explain the alternative.
5. What's the follow-up interviewers usually ask? "What if two nodes have the same row and column value — how do you break ties?" and "Can you do this with DFS instead of BFS?" (DFS requires tracking row explicitly and then sorting by row within each column, which is why BFS is preferred here).

Quick Revision

• Pattern: BFS + hash map bucketing by column index.
• Root starts at column 0; left child is col-1, right child is col+1.
• BFS queue holds (node, col) pairs, guaranteeing correct top-to-bottom, left-to-right order.
• Track min_col and max_col while traversing to avoid sorting dictionary keys afterward.
• Final result: iterate columns from min_col to max_col, appending each column's list.
• Empty tree returns [] immediately.
• Contrast with LC 987: that variant sorts same-row-and-column ties by value, not insertion order.
• DFS is possible but needs extra row tracking and a manual sort by row per column.

Related Problems

• LC 987 - Vertical Order Traversal (harder variant that sorts ties by value; not in this directory).
• Binary tree level-order traversal problems share the same BFS queue-based pattern (e.g. (node, level) tracking instead of (node, col)).
• Grouping/bucketing-by-key problems (hash map of lists keyed by a computed attribute) reuse the same "traverse once, bucket by key" technique.