Vertical Order Traversal of a Binary Tree

Draw the tree on graph paper. Not sketched loosely — drawn on a real grid, with real coordinates.

The root sits at the origin. Every time you go down-left, you move one square down and one square left. Every time you go down-right, you move one square down and one square right. That's it — that's the entire coordinate system.

Now here's the thing you're being asked for. Forget the branches. Forget parents and children. Just look at the piece of paper and the dots on it.

Return one list per strip. Skip strips with nothing in them.

That last rule — smaller number first when two nodes land on the same square — sounds like a footnote. It is not a footnote. It is the entire reason this problem is rated Hard instead of Medium, and it is the reason a perfectly reasonable solution you'll write in ninety seconds will fail.

Because yes: two different nodes can land on exactly the same square. A node deep in the left subtree that drifted right, and a node deep in the right subtree that drifted left, can collide on the same coordinate. They're unrelated. They've never met. And now you have to decide which one gets printed first, and the tree structure gives you no answer — so the problem hands you one: smaller value wins.

Reading strip by strip, left to right: [4], [2], then the middle strip — which contains 1 on row 0, and both 5 and 6 on row 2. Smaller first, so [1, 5, 6]. Then [3], then [7].

There are three traps here, stacked on top of each other. Most people fall into the first two, fix them, feel clever, and then get destroyed by the third.

Trap 1 — "I'll just DFS and bucket by column"

Completely natural. Recurse, carry a column number, dump values into a map keyed by column.

The problem: DFS visits in depth order, not row order. A node three levels deep in the left subtree gets visited long before a node one level deep in the right subtree — and they can share a column. So the list for that column comes out vertically scrambled.

Trap 2 — "Fine, BFS then, so rows come out in order"

Better! BFS is level order, so within any single column, nodes now genuinely appear top-to-bottom. Row ordering: solved, free, no extra work.

And this is where people get comfortable. This solution passes a satisfying number of test cases. It is also the accepted solution to a different problem — LeetCode 314, "Binary Tree Vertical Order Traversal," which has no tie-break rule.

Trap 3 — the one that actually fails you

Here's the exact test case that exposes it. Watch node 6 and node 5:

Node 6 is the right child of 2. Node 5 is the left child of 3. Both land at column 0, row 2. Same square. They are not siblings, not cousins in any useful sense — they just happen to have drifted into each other.

BFS reaches 2 before 3, so it emits 6 then 5. The answer requires 5 then 6. Your output is [1, 6, 5]; the expected output is [1, 5, 6]. One test case, and it's over.

Trap 4 (bonus) — negative columns

Columns go negative. You can't index an array with −2. And a HashMap gives you no ordering, so even after you've collected everything perfectly, printing it in hash order scrambles the strips. Small trap, but it catches people at the very last line.

Let me convince you properly, because this sounds like a restatement and it isn't.

Step 1 — read the problem's rules as a comparator

The problem tells you, in plain English, exactly how to compare any two nodes:

• Different column? The smaller column comes first.
• Same column, different row? The smaller row comes first.
• Same column, same row? The smaller value comes first.

Look at what that is. That is a total order on nodes. Given any two nodes in the tree, those three rules always produce a decisive answer. There are no unresolved ties, no "it depends," no ambiguity.

Step 2 — realise what that buys you

Any collection of items with a total order defined on them has exactly one correct sorted sequence. And any sorting algorithm will find it.

So the answer isn't something you have to discover through clever traversal. It's already determined the moment you know each node's triple. The output is a mathematical consequence of the data, not a consequence of the walk.

This is why the DFS-versus-BFS argument that dominates most explanations is a red herring. Use whichever you like. DFS is three lines shorter. Neither one affects correctness, because neither one is responsible for ordering.

Step 3 — why the coordinates work the way they do

The rule left → (row+1, col−1) and right → (row+1, col+1) is just a statement about drawing. Going left moves you left. Going down moves you down. There's nothing to derive.

But notice one consequence that does matter: the column is not unique to a node. Unlike the seat index in a perfect-tree layout, where each position belongs to exactly one node, here −1 + 1 = 0 and +1 − 1 = 0. Two entirely different paths can arrive at the same column. And if they also happen to be at the same depth, you get a genuine collision — which is precisely why the problem needs a third tie-break key.

Click any node to see its coordinate and light up its column strip.

Step 4 — see the comparator actually matter

Below is the same tree shape, with the root relabelled 9 so each broken comparator produces a visibly different answer. Switch the sort keys and watch the output break in four distinct ways.

Welcome to the village of Treeton, and its famously over-engineered post office. 📮

Treeton has one Main Street, running north to south, and it is numbered 0. Streets to the west are −1, −2, −3. Streets to the east are +1, +2, +3. The village council thought this was elegant. The postal service has never forgiven them.

Every building has a floor number too: floor 0 at the top of the hill, floor 1 below it, floor 2 below that. (Treeton is built into a hillside. Don't overthink it.)

So every letter that arrives has three things written on it:

Meet Priya, the postal clerk. Her job has exactly three phases, and she never mixes them up.

Phase 1 — stamping. The letters arrive in a jumbled sack, in no useful order whatsoever. Priya doesn't care. She picks up each letter and stamps the street and floor onto it. She does this in whatever order the letters come out of the sack, because the order she stamps them in has no bearing on anything. Stamping is not sorting.

Phase 2 — pigeonholes. Behind her is a wall of pigeonholes, one per street, arranged west to east: −2, −1, 0, +1, +2. She throws each stamped letter into the hole for its street.

Phase 3 — ordering each hole. Now she takes each pigeonhole and puts its letters in delivery order: lowest floor first, because the postman walks downhill. And here's the rule from the manual, Section 4, subclause (c):

Then she walks the pigeonholes west to east and hands out the bundles. Done.

The subplot: Bob

Last summer the post office hired a temp named Bob. Bob noticed that the mail truck always delivers letters floor by floor — all the floor-0 letters, then all the floor-1 letters, and so on. Bob concluded, reasonably, that the truck had already done the sorting for him, and he could just stack letters into pigeonholes in arrival order and skip Phase 3 entirely.

Bob was right about floors. Bob was catastrophically wrong about §4(c).

Two letters arrived for street 0, floor 2: one for Six, one for Five. The truck had picked up Six first, because Six lives on the eastern edge of the western district and the truck goes west to east. Bob stacked Six, then Five. The postman delivered them in that order. Section 4(c) was violated. There was an inquiry.

Bob is the BFS-only solution. Bob is what you write in the first ninety seconds. Don't be Bob.

Cast list

Remember Priya's three phases: stamp, file, order. Never let them bleed into each other, and this problem cannot hurt you.

Let's invent this from nothing, failing our way forward.

Attempt 0 — "DFS, bucket by column"

Columns are right. Contents are scrambled. On the tree [3,9,20,null,null,15,7], column 0 gets 3 first and 15 later, which happens to be fine — but flip the shape and a deep left node beats a shallow right node into the same bucket. ❌

Lesson: depth order ≠ row order. We need row information.

Attempt 1 — "BFS instead"

Now nodes enter each bucket in genuine top-to-bottom order, free of charge, because BFS is level order. Rows: solved. ✅

Then you hit [1,2,3,4,6,5,7] and get [1,6,5] instead of [1,5,6]. ❌

Lesson: BFS orders rows, but within a row it orders by tree position, and tree position is not value.

Attempt 2 — "Patch it: sort each row's slice"

Since BFS already isolates one row at a time, collect that row's (col, value) pairs into a small list, sort it by (col, value), then flush it into the buckets. Ties inside a row are now resolved by value, and rows still arrive in order.

This works. It's a genuinely good solution. But notice what just happened: you gave up on the traversal doing the ordering, and started sorting. You just did it in small batches.

Attempt 3 — "Why am I sorting in batches?"

Ask the honest question: if I'm sorting anyway, why am I bending the traversal into level order to help? What if I sort everything, once?

And now the traversal genuinely doesn't matter — use a three-line DFS. Every ordering requirement lives in one comparator, where you can read it and check it against the problem statement line by line.

Attempt 4 — "Can I make the data structure do the sorting?"

Yes, and it's worth knowing because interviewers sometimes like it:

Insert every node and the structure maintains all three orderings automatically; then you just walk it. It's elegant and it reads beautifully. It's also slower in practice (three levels of tree-map overhead per insert), more allocation, and much easier to fumble under pressure. Know it, mention it, don't lead with it.

The final algorithm

1. DFS from the root with (row = 0, col = 0). Recurse left with (row+1, col−1), right with (row+1, col+1).
2. At each node, append the triple {col, row, value} to a flat list.
3. Sort the list: by col, then row, then value.
4. Walk the sorted list; start a new output group every time col changes.

Tree: [1, 2, 3, 4, 6, 5, 7] — the collision case.

Watch the three phases stay strictly separate: stamp (assign coordinates, in DFS preorder), sort (one comparator, everything at once), group (walk and cut on column change).

The moment that matters

Look back at the stamping phase. Node 6 was stamped fourth and node 5 was stamped sixth — DFS reached 6 long before 5. Look at the sorted list: 5 comes before 6.

The sort completely erased the traversal's opinion. That's not a side effect; that's the design. The traversal was never allowed to have an opinion in the first place.

For each line, one question: what disaster happens if we delete it or change it? Click to open.

Thirteen ways this goes wrong, roughly ordered by how often they actually happen in interviews.

Trigger words in the prompt

• "vertical," "column," "same column," "left to right"
• "top to bottom," "row," "position (row, col)"
• "if two nodes are in the same position / same row and column, order by value" — this sentence is the problem. The moment you see it, you know there are three sort keys, and you know the naive traversal solution is wrong.
• Any explicit statement of the form "sort by A, then by B, then by C"

Structural tells

• The problem describes the output order in words rather than implying it from a traversal. That's a comparator specification in disguise.
• The output is grouped by something that isn't depth.
• Two nodes with no relationship to each other can compete for the same output slot.

The wider family — every one of these is "assign a coordinate, then order by it":

And the one that encodes the actual comparator:

If you remember nothing else six months from now, remember Priya's three phases — stamp, file, order — and remember Bob, who thought the truck had already sorted his letters and got hauled into an inquiry over Section 4(c). Those two images regenerate the whole solution, including the part everyone forgets.

The interviewer asks: "Walk me through your approach." Here is the answer, near-verbatim.

The three beats, if you forget the script

The whole lesson, compressed to the size of an index card.