Special Traversals

What is this?

A few tree problems don't care about the usual visiting orders at all — they want the output arranged by where things sit in space, like reading a tree column by column. The trick is to give every node a pair of coordinates (its row and column) as you walk through, completely ignoring the tree's shape. Once each node carries a position, the whole problem turns into something simple: sort the nodes by their coordinates.

💡 Fun fact: This is the same idea behind how a spreadsheet or a screen lays things out — every cell or pixel has a coordinate, so arranging them is just sorting by position.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

Core idea: Some tree problems don't ask for inorder/preorder/level order at all — they ask for an output defined by position (columns, rows, diagonals). The trick is to stop thinking about tree shape and assign every node a coordinate, then the answer is just a multi-key sort of those coordinates.

Coordinates over shape

Once each node carries (row, col), the tree's branching is irrelevant — you collect tuples and sort. Getting the tie-break order exactly right (column, then row, then value) is where most solutions break.

The problem

• Vertical Order Traversal of a Binary Tree — assign (row, col), group by column left-to-right, and within a column sort by row then by value for same-cell collisions.

Key takeaways

• Give nodes coordinates — a geometric output contract becomes a sort.
• Mind the tie-break — column, then row, then value; the value tie-break is the classic bug.
• Tree shape stops mattering once every node has a position.
• Why interviewers love it: it checks whether you can translate an unusual output spec into a precise comparator.

Problem: Vertical Order Traversal of a Binary Tree.