Problem Statement
Given the root of a binary tree, return its vertical order traversal.
Rules:
- Nodes are grouped by their column (Horizontal Distance).
- If multiple nodes share the same row and column, sort them by value.
Brute Force Intuition
In an interview, you can explain it like this:
Traverse every node, store its row and column information, then sort all collected nodes based on column, row, and value.
Although correct, sorting all nodes together becomes expensive.
Complexity
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Moving Towards the Optimal Approach
Observe that every node has:
Column (Horizontal Distance)
+
Row (Depth)
If we store nodes using:
Column
↓
Row
↓
Values
we can build the answer naturally.
Pattern Recognition
Whenever you see:
- Vertical Traversal
- Column-wise Traversal
- Horizontal Distance
Think:
BFS + Ordered Maps
Key Observation
Assign coordinates:
Root
↓
(Row = 0, Col = 0)
Rules:
Left Child
↓
(Row + 1, Col - 1)
--------------------
Right Child
↓
(Row + 1, Col + 1)
Store nodes as:
TreeMap<
Column,
TreeMap<
Row,
PriorityQueue<Values>
>
>
Optimal Approach
Step 1
Perform BFS.
Store:
(Node, Row, Column)
Step 2
Insert into:
column
↓
row
↓
priority queue
Step 3
Traverse:
Columns
↓
Rows
↓
Sorted Values
Optimal Java Solution
class Pair {
TreeNode node;
int row;
int col;
Pair(TreeNode node,
int row,
int col) {
this.node = node;
this.row = row;
this.col = col;
}
}
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
TreeMap<Integer,
TreeMap<Integer,
PriorityQueue<Integer>>> map =
new TreeMap<>();
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(root, 0, 0));
while (!q.isEmpty()) {
Pair curr = q.poll();
map.putIfAbsent(curr.col,
new TreeMap<>());
map.get(curr.col)
.putIfAbsent(curr.row,
new PriorityQueue<>());
map.get(curr.col)
.get(curr.row)
.offer(curr.node.val);
if (curr.node.left != null)
q.offer(new Pair(
curr.node.left,
curr.row + 1,
curr.col - 1));
if (curr.node.right != null)
q.offer(new Pair(
curr.node.right,
curr.row + 1,
curr.col + 1));
}
List<List<Integer>> ans =
new ArrayList<>();
for (TreeMap<Integer,
PriorityQueue<Integer>> rows
: map.values()) {
List<Integer> list =
new ArrayList<>();
for (PriorityQueue<Integer> pq
: rows.values()) {
while (!pq.isEmpty())
list.add(pq.poll());
}
ans.add(list);
}
return ans;
}
}
Dry Run
3
/ \
9 20
/ \
15 7
Coordinates:
9
↓
(-1,1)
3
↓
(0,0)
15
↓
(0,2)
20
↓
(1,1)
7
↓
(2,2)
Vertical Order:
9
↓
3 15
↓
20
↓
7
Answer:
[[9],[3,15],[20],[7]]
Why BFS + Ordered Maps Work?
Every node is assigned:
Column
↓
Row
TreeMap automatically sorts:
Columns
↓
Rows
PriorityQueue handles nodes that share the same row and column.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N log N) |
| Space Complexity | O(N) |
Interview One-Liner
Perform BFS while tracking row and column indices, then store nodes in nested TreeMaps with a PriorityQueue to maintain the required ordering.
Pattern Learned
BFS
↓
(Row, Column)
↓
Ordered Maps
↓
Vertical Traversal
Similar Problems
- Vertical Order Traversal
- Top View
- Bottom View
- Vertical Sum
- Diagonal Traversal
Memory Trick
Think:
Node
↓
(Row, Column)
↓
TreeMap
↓
PriorityQueue
↓
Answer
Mental Model
Tree
↓
Assign Coordinates
↓
Group By Column
↓
Sort By Row
↓
Output
Whenever you hear:
"Vertical Order Traversal"
your brain should immediately think:
BFS + (Row, Column) Coordinates + TreeMap
SOCIAL SHARE CARD GENERATOR