Vertical Order Traversal
WHAT IT SAYS
Group the tree's nodes into vertical columns — left child one column left, right child one column right — and report the columns from leftmost to rightmost, top to bottom within each.
WHAT IT'S REALLY ASKING
"The word 'vertical' is not a tree concept at all; it is a GEOMETRY concept. Give every node an (x, y) coordinate — column and depth — and the tree dissolves into a set of labelled points. What is left is not a traversal problem. It is a sorting problem."
One pass per column
O(n * width) time — a full traversal per columnFirst find the leftmost and rightmost column indices. Then for each column c from min to max, traverse the entire tree and emit the nodes whose column equals c.
WHERE THE WORK IS WASTED — Each traversal visits all n nodes to keep the few in one column, discarding perhaps 95 percent of its work — and then the next traversal re-walks the identical tree, re-computes the identical column index for every node, and keeps a different sliver. The column of a node never changes between passes; you are recomputing a static labelling width-many times because you refuse to write it down the first time.
Assign coordinates once, and the tree becomes sortable points.
The column of a node is determined by the path from the root: start at 0, subtract 1 for every left step, add 1 for every right step. Depth is the step count. Both labels are computable during any single traversal, in O(1) per node, handed from parent to child. One pass, and every node carries (column, depth, value). Now notice what happened to the problem. 'Vertical order traversal' asked you to output the nodes sorted by column, then by depth within a column. That is not a statement about trees — it is a sort key. The tree's only remaining job was to GENERATE the labelled points; once they exist, the tree is irrelevant and the answer is sort-by-(column, depth), then group by column. A problem about a pointer structure just became a problem about tuples, and tuples are a solved problem. One genuine subtlety survives, and it is where implementations diverge: what breaks the tie when two nodes share BOTH column and depth? The tree has no natural answer — DFS visit order depends on arbitrary choices — so the problem must legislate. LeetCode's version says: sort ties by value. Other statements say: preserve left-to-right order, in which case BFS delivers it for free (BFS visits a level strictly left to right, so equal-depth nodes arrive pre-ordered) while DFS does not. Read which contract you are under before writing a comparator; this single clause is the difference between accepted and wrong-answer on an otherwise identical solution. The grouping structure follows taste: a map from column to list, filled during the walk and read out in sorted-column order, or one flat list of triples sorted at the end. Same information, same complexity.
One labelled walk, one sort
O(n log n) time for the sort — O(n) if you use BFS plus a sorted map and the tie-break is left-to-right — O(n) spaceTraverse once (BFS or DFS), passing (column, depth) to children as (c-1, d+1) and (c+1, d+1), collecting triples. Sort by column, then depth, then the legislated tie-break. Group consecutive equal columns into the output lists.
Label With Coordinates, Then Sort
YOU'LL SEE IT AGAIN WHEN
- The required grouping or order is spatial — columns, diagonals, distance — rather than structural, so it is a function of a coordinate you can assign top-down.
- The label of each element is O(1) computable from its parent's label, so one traversal annotates everything.
- Ties need a legislated rule the structure cannot supply — a sign that the real deliverable is a sort key, not a traversal.