Vertical Order Traversal of a Binary Tree: Coordinate Sorting

Given the root of a binary tree, return the vertical order traversal of its nodes' values. For each node at position (row, col), its left child is at (row + 1, col - 1) and its right child is at (row + 1, col + 1). The root starts at (0, 0). Return the traversal as a list of lists, from the leftmost column to the rightmost. Within a column, nodes are ordered by row first, then by value if they share the same row.

This is LeetCode 987: Vertical Order Traversal of a Binary Tree.

For example, given root = [3, 9, 20, null, null, 15, 7], the output is [[9], [3, 15], [20], [7]]. Node 3 and node 15 share column 0, but node 3 is in row 0 and node 15 is in row 2, so 3 comes first.

Why this problem matters

Vertical order traversal combines tree traversal with coordinate geometry and sorting. You need three skills working together: traversing the tree to assign coordinates, sorting those coordinates by a multi-key rule, and grouping results by column. Each skill on its own is basic. The challenge is wiring them together cleanly.

This problem also shows up as a harder variant of LeetCode 314: Binary Tree Vertical Order Traversal. The difference is the tiebreaker. In 314, nodes at the same row and column keep their left-to-right BFS order. In 987, they are sorted by value. That one difference pushes you toward a sort-based approach instead of pure BFS.

Brute force

def vertical_traversal(root):
    coords = []

    def dfs(node, row, col):
        if not node:
            return
        coords.append((col, row, node.val))
        dfs(node.left, row + 1, col - 1)
        dfs(node.right, row + 1, col + 1)

    dfs(root, 0, 0)
    coords.sort()
    result = []
    prev_col = None
    for col, row, val in coords:
        if col != prev_col:
            result.append([])
            prev_col = col
        result[-1].append(val)
    return result

This is already the optimal approach. The brute force would be to collect all nodes, then for each unique column iterate through the entire list to extract that column's nodes. That wastes time re-scanning. But the DFS-plus-sort version above does everything in one pass plus a sort. For a tree problem, there is no way to avoid visiting every node, so the real question is how efficiently you process the coordinates after collecting them.

The key insight

Think of the tree as a 2D coordinate system. The root sits at (0, 0). Every left move shifts the column by -1 and the row by +1. Every right move shifts the column by +1 and the row by +1. Once you label every node with its (row, col), the problem reduces to sorting tuples.

The sort key is (col, row, value). Sorting by column first groups nodes into their vertical slices. Within the same column, sorting by row puts higher nodes before lower ones. And if two nodes share the same column and row, sorting by value breaks the tie. After sorting, you just group consecutive entries with the same column into sublists.

Walking through it

Let's trace through the tree [3, 9, 20, null, null, 15, 7]. Watch how DFS assigns coordinates and how sorting produces the final grouping.

DFS visits every node and stamps it with a (col, row, value) tuple. After all nodes are visited, sorting by (col, row, value) puts them in the right order. Grouping consecutive entries by column produces the final answer: [[9], [3, 15], [20], [7]].

Notice that node 3 at (0, 0) and node 15 at (0, 2) share column 0. Since row 0 comes before row 2, node 3 appears first in that column's list. If two nodes shared the same row and column, the smaller value would come first.

Solution

from collections import defaultdict

def vertical_traversal(root):
    coords = []

    def dfs(node, row, col):
        if not node:
            return
        coords.append((col, row, node.val))
        dfs(node.left, row + 1, col - 1)
        dfs(node.right, row + 1, col + 1)

    dfs(root, 0, 0)
    coords.sort()
    result = []
    prev_col = None
    for col, row, val in coords:
        if col != prev_col:
            result.append([])
            prev_col = col
        result[-1].append(val)
    return result

Here is what each part does:

• coords = [] collects (col, row, value) triples for every node in the tree.
• dfs(node, row, col) recurses through the tree. Left children get col - 1, right children get col + 1, and both get row + 1.
• coords.sort() sorts the triples. Python's tuple sort compares element by element: column first, then row, then value. This single sort handles all three tiebreaking rules at once.
• The grouping loop scans through the sorted coordinates. Whenever the column changes, it starts a new sublist. Since the list is sorted by column, all entries for the same column are consecutive.

Complexity analysis

The sorting step dominates the time complexity. You cannot avoid it because the problem requires ordering by value when two nodes share the same row and column. If the tiebreaker were just insertion order (as in LeetCode 314), you could use BFS and skip the sort entirely.

Building blocks

This problem is built on two reusable patterns:

1. DFS with coordinate tracking. Pass (row, col) as parameters through the recursion. At each node, record the coordinates and recurse with updated values. This pattern appears whenever you need to assign spatial positions to tree nodes:

def dfs(node, row, col):
    if not node:
        return
    record(row, col, node.val)
    dfs(node.left, row + 1, col - 1)
    dfs(node.right, row + 1, col + 1)

2. Multi-key sort and group. Collect items as tuples with the sort key built in, sort once, then scan linearly to group by the primary key. This is a general technique that works whenever you need to partition sorted data into buckets:

items.sort()
groups = []
prev_key = None
for key, *rest in items:
    if key != prev_key:
        groups.append([])
        prev_key = key
    groups[-1].append(rest)

Edge cases

• Empty tree (root is None): return an empty list []. The DFS never runs, and coords stays empty.
• Single node (no children): return [[root.val]]. The only coordinate is (0, 0, root.val).
• Same row and column, different values: two nodes can land on the same (row, col) if the tree branches and reconverges. The sort by value handles this: smaller values come first within the same position.
• Left-skewed tree: every node shifts one column to the left. Each column has exactly one node, so the output is a list of single-element lists.
• Complete binary tree: the column range spans from -depth to +depth. Nodes at opposite edges of the tree can share columns with nodes deeper in the tree.

Common mistakes

• Forgetting the value tiebreaker. LeetCode 314 does not sort by value when two nodes share the same row and column. LeetCode 987 does. If you confuse the two, you will pass some test cases but fail on inputs where nodes overlap at the same position.
• Using BFS order as tiebreaker. BFS naturally visits nodes left to right, which works for 314 but not 987. For 987 you must sort by value, not by insertion order.
• Sorting by (row, col, value) instead of (col, row, value). Column must be the primary sort key because the output groups by column. Sorting by row first would interleave columns.

From understanding to recall

You just traced through a DFS that assigns coordinates and a sort that produces the final grouping. The solution is clean: collect tuples, sort, group. It makes sense right now. But in an interview, will you remember that the sort key is (col, row, value) and not (row, col, value)? Will you remember to group by column after sorting rather than using a hash map?

Understanding a solution is not the same as producing it under pressure. Spaced repetition bridges that gap. You practice writing the DFS coordinate assignment and the sort-and-group loop from memory at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the tuple structure and the grouping logic until the pattern is automatic.

DFS with coordinate tracking and multi-key sort-and-group are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Right Side View - Another tree traversal that extracts specific nodes by their position, using BFS instead of coordinate sorting
• Binary Tree Level Order Traversal - The base BFS level-by-level pattern that many tree traversal problems build on
• Binary Tree Zigzag Level Order Traversal - A BFS variation that alternates direction, showing how traversal order affects output structure

CodeBricks helps you internalize these tree traversal patterns so they become automatic. Instead of re-deriving the coordinate system and sort key from scratch every time, you build muscle memory through targeted repetition. The DFS-with-coordinates pattern and the sort-and-group pattern each get their own drill, so you can practice them independently and combine them when this problem comes up.