Vertical Order Traversal of a Binary Tree
Return a binary tree's values column by column, top to bottom, breaking same-position ties by value, by tagging each node with its column and row and sorting.
Problem Understanding
Vertical Order Traversal of a Binary Tree: the root is at (row 0, column 0); a node at (row, col) has its left child at (row + 1, col − 1) and right child at (row + 1, col + 1). Return the values column by column from left to right; within a column, top to bottom, and nodes in the same row and column sorted by value.
Examples: [3,9,20,null,null,15,7] → [[9],[3,15],[20],[7]]; [1,2,3,4,5,6,7] → [[4],[2],[1,5,6],[3],[7]].
The Intuition: Coordinates, Then One Sort
Every node has a coordinate, and the required output order is just a sort on it:
- Tag every node with (column, row) during a DFS, passing coordinates down as in Maximum Depth of Binary Tree.
- Sort by (column, row, value): left to right, top to bottom, ties by value.
- Group consecutive triples with the same column.
A level-by-level view of the same tree is Binary Tree Level Order Traversal, which groups by row instead of column.
Interactive Walkthrough
c:N = COLUMN · LEFT CHILD −1, RIGHT CHILD +1
ROOT = (ROW 0, COL 0)
tagged
0
columns
:
columns, left to right
After the sort
Root is row 0, column 0. A left child is one row down and one column left; a right child, one row down and one column right
Next
1 is at row 0, column 0: record (0, 0, 1)
root
During the DFS each node shows its column under it. After the sort, nodes join their column's group one by one, and the groups are listed beside the tree. Try Example 3 for the value tie-break.
Dry Run Table
Input: [1,2,3,4,5,6,7].
| Node | Row | Column |
|---|---|---|
| 1 | 0 | 0 |
| 2, 3 | 1 | −1, 1 |
| 4, 5 | 2 | −2, 0 |
| 6, 7 | 2 | 0, 2 |
Sorted by (column, row, value): (−2,2,4) (−1,1,2) (0,0,1) (0,2,5) (0,2,6) (1,1,3) (2,2,7).
Answer: [[4],[2],[1,5,6],[3],[7]]. 5 and 6 share row 2 and column 0, so they appear in value order.
The Solution Template
Tag, sort, group.
Vertical Order Traversal of a Binary Tree Code
1var verticalTraversal = function(root) {2 const nodes = [];3 const dfs = (node, row, col) => {4 if (!node) return;5 nodes.push([col, row, node.val]);6 dfs(node.left, row + 1, col - 1);7 dfs(node.right, row + 1, col + 1);8 };9 dfs(root, 0, 0);10 nodes.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);11 const result = [];12 let last = null;13 for (const [col, , val] of nodes) {14 if (col !== last) {15 result.push([]);16 last = col;17 }18 result[result.length - 1].push(val);19 }20 return result;21};
Edge Cases & Common Mistakes
- Ties within a row and column: sort them by value, not by visit order.
- Sorting by column only: loses the top-to-bottom order.
- Single node:
[[root.val]]. - Skewed trees: columns run from −(n−1) to 0 or 0 to n−1; no fixed-size array of columns.
- Confusing with LeetCode 314: that version breaks ties by BFS order.
Summary
Record (column, row, value) for every node, sort those triples, and split the sorted list by column. O(n log n) time, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet