Vertical Order Traversal
Group all nodes by column, then by row, then by value; return columns from left to right.
Key concepts at a glance — for those who already know the basics.
Problem Statement
Vertical Order Traversal of a Binary Tree
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [[4], [2], [1, 5, 6], [3], [7]]
Constraints
- The number of nodes in the tree is in range [0, 1000].
- Node values are in range [-1000, 1000].
01 · The rule
Assign each node a (col,row), group by col, sort each group by (row,val), then return columns left to right.
Root: (0,0). Left child: col-1. Right child: col+1. Every level adds row+1.
02 · The key difference
Top/Bottom view
Keeps one node per column.
Vertical order
Keeps all nodes per column and sorts deterministically.
03 · How to think
BFS with (node, col, row)
Root is (0,0). Left child is (col-1,row+1), right child is (col+1,row+1).
Build colMap
Append (row,val) into each column bucket. Never overwrite existing values.
Sort each bucket
Sort by (row,val) so ties on same row are resolved by value.
Read columns left to right
Sort column keys and output values for each column.
04 · Diagram
Final answer: [[4], [2], [1,5,6], [3], [7]]
05 · Code
from collections import defaultdict, deque
def verticalOrder(root):
if not root:
return []
col_map = defaultdict(list)
queue = deque([(root, 0, 0)])
while queue:
node, col, row = queue.popleft()
col_map[col].append((row, node.val))
if node.left:
queue.append((node.left, col-1, row+1))
if node.right:
queue.append((node.right, col+1, row+1))
result = []
for col in sorted(col_map):
sorted_nodes = sorted(col_map[col])
result.append([v for _, v in sorted_nodes])
return result06 · Complexity
Time
O(n log n)
BFS O(n) + sorting O(n log n).
Space
O(n)
Queue and col_map together hold all nodes.
07 · Interview uses
LeetCode 987: Exact same ordering contract. Tie-handling on same (col,row) is the key differentiator.
Top/Bottom view relation: Both are reduced forms of this coordinate model with one-node-per-column selection.
Column-wise tree output: Any vertical grouping output relies on the same col,row representation.
BFS + metadata confidence: Demonstrates queue-state modeling and deterministic post-processing.
Ready to see it in action?
Step through the visualizer to watch the algorithm state update live.