Vertical Order Traversal
MediumGive each node a (column, row) coordinate
Problem
Return the vertical order traversal of a binary tree grouped by column (root column = 0).
Assign each node a column (parent-1 left, parent+1 right) and read columns left to right.
The idea
Assign the root column 0, decrementing left and incrementing right, and carry the depth as the row. Grouping nodes by column and sorting within a column by row — and by value for ties — produces the vertical order.
The trick
- Left child is column-1, right is column+1; depth is the row.
- Ties at the same cell are broken by value.
- BFS gives rows in order for free; DFS needs an explicit sort.
Step 1 of 5. Level-order BFS: snapshot the queue size to process exactly one level per iteration.
Fix the level width up front.
1const q = [root], out = [];2while (q.length) {3 const level = [];4 for (let n = q.length; n > 0; n--) {5 const node = q.shift();6 level.push(node.val);7 if (node.left) q.push(node.left);8 if (node.right) q.push(node.right);9 }10 out.push(level);11}Input
- nodes
- 6, 5 edges
Memory
- levels
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [3,9,20,null,null,15,7]
- Output:
- [[9], [3, 15], [20], [7]]
- Explanation:
- Group nodes by their column, left to right.
Example 2
- Input:
- tree = [1,2,3]
- Output:
- [[2], [1], [3]]
- Explanation:
- [[2],[1],[3]].
Example 3
- Input:
- tree = [1]
- Output:
- [[1]]
- Explanation:
- [[1]].
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.