Vertical Order Traversal
Group nodes by column (left child −1, right +1); within a column sort by row, ties by value.
Open on LeetCode ↗02
Intuition
Every node has a 2-D coordinate: (row, col) assigned by the traversal. Collect (col, row, val) triples with any DFS, then sort — the whole problem is coordinates plus a well-defined ordering.
03
Approach
1
Assign coordinates
Root (0,0); left child (row+1, col−1); right child (row+1, col+1). One DFS collects all triples.
2
Group by column
Bucket triples by col (a dict), columns read left to right — sort the keys.
3
Order inside a column
Sort each bucket by (row, val) — the value tiebreak is the spec's subtle requirement.
04
Solution & live demo
python
▶1from collections import defaultdict
▶2
▶3class Solution:
▶4 def verticalTraversal(self, root):
▶5 cols = defaultdict(list)
▶6 def dfs(node, r, c):
▶7 if not node: return
▶8 cols[c].append((r, node.val))
▶9 dfs(node.left, r + 1, c - 1)
▶10 dfs(node.right, r + 1, c + 1)
▶11 dfs(root, 0, 0)
▶12 return [[v for _, v in sorted(cols[c])] for c in sorted(cols)]
05
Edge cases
Two nodes at same (row, col)
The value tiebreak orders them — required by the problem.
Skewed tree
Columns spread −n..0 or 0..n; dict handles sparse keys.
06
Complexity
Time
O(n log n)
Space
O(n)
Sorting dominates.