987 · Vertical Order Traversal of a Binary Tree

Every node gets two coordinates instead of one: a column (how far left or right of the root) and a row (how deep). Group by column, then settle every tie the same deterministic way — by row, then by the node's own value.

1 — The problem, and the three-way sort it hides

Assign the root column 0. A left child is one column left of its parent, a right child one column right; every child is one row below its parent. Group all nodes by column, left to right, and within a column, order by row, top to bottom. That much matches most people's first instinct — and it's not the whole rule.

The rule that trips people up: two different nodes can land on the exact same row and the same column, arriving there via completely different paths from the root. When that happens, order them by value, ascending. Skip that clause and the traversal is only accidentally correct on trees where no such collision occurs.

The example below is chosen specifically because it collides: node 5 (reached via 1 → 3 → 5) and node 6 (reached via 1 → 2 → 6) land on the same row and the same column, from opposite sides of the tree.

2 — Visualizing the two phases

2.1 Phase one: assign coordinates with a DFS

A single depth-first pass gives every node its (row, col) pair. The recursion needs nothing more than the two coordinates threaded down as parameters.

record Item(int val, int row, int col) {}List<Item> items = new ArrayList<>();void dfs(TreeNode nd, int row, int col) {    if (nd == null) return;    items.add(new Item(nd.val, row, col));    dfs(nd.left,  row + 1, col - 1);    dfs(nd.right, row + 1, col + 1);}items.sort(Comparator.comparingInt(Item::col)    .thenComparingInt(Item::row)    .thenComparingInt(Item::val));

Watch for the moment nodes 5 and 6 both show up at row 2, col 0. Nothing in the DFS itself notices the collision — it only becomes visible once the global sort runs, which is exactly why the sort key has to include value as a tie-breaker: row and column alone aren't a unique identifier for a node's position.

2.2 Phase two: group by column

Once every item carries a fully-resolved sort order, grouping is a single linear pass: walk the sorted list, and whenever the column changes, start a new output list.

3 — Complexity and edge cases

• Time: O(n log n) — the DFS pass is O(n), but the global sort over all n items dominates.
• Space: O(n) for the coordinate list and the grouped output.
• A left-only or right-only chain never collides — every node in a pure left spine gets a strictly decreasing column and a strictly increasing row, so the value tie-break never actually fires. It only matters on trees with nodes from different branches converging on the same cell.
• Duplicate values are allowed by the problem, so even the value tie-break can theoretically tie — at that point any stable order between the two identical values is acceptable, since they're indistinguishable in the output.
• Empty tree: empty result.

4 — Reference implementation

public List<List<Integer>> verticalTraversal(TreeNode root) {
    record Item(int val, int row, int col) {}
    List<Item> items = new ArrayList<>();

    new Object() {
        void dfs(TreeNode nd, int row, int col) {
            if (nd == null) return;
            items.add(new Item(nd.val, row, col));
            dfs(nd.left,  row + 1, col - 1);
            dfs(nd.right, row + 1, col + 1);
        }
    }.dfs(root, 0, 0);

    items.sort(Comparator.comparingInt(Item::col)
        .thenComparingInt(Item::row)
        .thenComparingInt(Item::val));

    List<List<Integer>> result = new ArrayList<>();
    int prevCol = Integer.MIN_VALUE;
    for (Item it : items) {
        if (it.col() != prevCol) { result.add(new ArrayList<>()); prevCol = it.col(); }
        result.get(result.size() - 1).add(it.val());
    }
    return result;
}