Vertical Order Traversal of a Binary Tree — Solution

Problem

Given a binary tree, return all node values grouped column by column from leftmost to rightmost. Within each column, nodes appear top to bottom by depth, and when two nodes share the same depth and column they are listed in ascending order by value.

[3,9,20,null,null,15,7]

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: [[9], [3, 15], [20], [7]]
• Explanation: 9 sits in column -1; column 0 holds 3 (depth 0) then 15 (depth 2); 20 is in column 1; 7 is in column 2.

To see why value-sorting matters, consider a perfectly balanced tree where two nodes land on the same (column, depth):

[1,2,3,4,5,6,7]

• Input: root = [1, 2, 3, 4, 5, 6, 7]
• Output: [[4], [2], [1, 5, 6], [3], [7]]
• Explanation: Nodes 5 (left child of 2) and 6 (left child of 3) both land at column 0, depth 2 — they must appear sorted as [5, 6], not in BFS insertion order.

Intuition

Treat the tree as a coordinate grid: the root sits at (col=0, row=0), each left child shifts one column left and one row down, and each right child shifts one column right and one row down. Once every node has a (col, row, val) triple, sorting those triples lexicographically handles all three tie-breaking levels at once — the column groups fall out naturally from a single scan of the sorted list.

Solution — BFS + Sort

Use BFS to assign coordinates to every node in a single pass, then sort the collected triples and group by column.

1. Push (root, col=0, row=0) onto a BFS queue.
2. For each dequeued entry, record (col, row, val) and enqueue the left child at (col-1, row+1) and right child at (col+1, row+1).
3. Sort all recorded triples by (col, row, val) — this single sort enforces column order, then depth order within a column, then value order for same-position ties.
4. Scan the sorted list; start a new output group each time col changes.
5. Return the list of column groups.

1from collections import deque
2
3def verticalTraversal(root):
4    if not root:
5        return []
6
7    node_positions = []
8    queue = deque([(root, 0, 0)])  # (node, col, row)
9
10    while queue:
11        node, col, row = queue.popleft()
12        node_positions.append((col, row, node.val))
13
14        if node.left:
15            queue.append((node.left, col - 1, row + 1))
16        if node.right:
17            queue.append((node.right, col + 1, row + 1))
18
19    # tuple comparison sorts col → row → val, resolving all ties automatically
20    node_positions.sort()
21
22    result = []
23    current_col = None
24    for col, row, val in node_positions:
25        if col != current_col:
26            result.append([])
27            current_col = col
28        result[-1].append(val)
29
30    return result

Time: O(n log n) — BFS visits each node once in O(n); sorting the n triples dominates at O(n log n).
Space: O(n) — the queue and positions list each hold at most n entries simultaneously.

Complexity Summary

Common Mistakes

• Ignoring value-based tie-breaking: when two nodes share the same (col, row), they must be output in ascending value order, not BFS insertion order. Sorting the full triple (col, row, val) handles this automatically; sorting only by (col, row) does not.
• Trusting BFS order for row sequencing within a column: BFS guarantees nodes are visited level by level, but siblings at the same level sharing a column still need value-sorting. Always sort the collected positions rather than relying on traversal order.
• Swapping left and right column offsets: left children decrease the column (col - 1) and right children increase it (col + 1). Reversing these flips the entire output horizontally.
• Skipping the null-root guard: accessing root.val before checking root is None raises an error on an empty-tree input, which is always a valid test case.
• Using DFS without recording rows: DFS can assign coordinates correctly if row is tracked, but returning nodes in DFS visit order within a column does not guarantee depth ordering — always collect and sort rather than building output incrementally during traversal.

Related Problems

• Binary Tree Level Order Traversal — same BFS backbone, groups nodes by row instead of column
• Binary Tree Zigzag Level Order Traversal — BFS with alternating row direction, a different axis grouping
• Binary Tree Right Side View — BFS selecting the rightmost node per level, column-awareness variant
• Maximum Width of Binary Tree — assigns virtual column indices to nodes to measure horizontal span at each level
• All Nodes Distance K in Binary Tree — BFS on a tree with coordinate-like distance tracking from a target node