Vertical Order Traversal

Vertical Order Traversal asks you to read a binary tree by columns instead of by rows. Imagine dropping vertical lines through the tree: every node lands on one of those lines, and we want the values grouped line by line, left to right. The trick is to give each node a horizontal distance and let a hash map do the bookkeeping.

The slow way first

You could try to compute each node's screen x-coordinate with real pixel math, then sort everything by x. That works, but it is fiddly: you have to track widths, avoid floating-point drift, and sort a big flat list at the end. It hides the simple structure underneath.

The question to ask: what actually decides which column a node belongs to? Only its path from the root — every left turn shifts it one column left, every right turn shifts it one column right. We can track that with a single integer.

The idea: a horizontal distance plus a column map

Give the root a horizontal distance hd = 0. A left child gets hd - 1, a right child gets hd + 1. Nodes that end up with the same hd share a column. Now do a BFS from the root, carrying each node's hd alongside it in the queue. As each node comes off the queue, append its value to cols[hd]. BFS visits the tree top-down, so within a column the values land in the correct top-to-bottom order automatically. At the end, read the columns in increasing hd order.

The key insight: because BFS processes the tree level by level, we never have to sort within a column — only the column keys themselves get sorted at the very end.

Walk through it

Step through the animation. BFS pops nodes in the order 1, 2, 3, 4, 5, 6, 7. Each pop appends to a column keyed by hd: 1 opens column 0, then 2 opens -1, 3 opens +1, and 4 opens -2. When 5 is popped it has hd 0, so column 0 grows to [1, 5]; then 6 (the left child of 3) is also hd 0, so column 0 becomes [1, 5, 6]. Finally 7 opens +2. Reading columns from hd -2 up to hd +2 gives the answer [[4], [2], [1, 5, 6], [3], [7]].

Pseudocode

if the tree is empty: return []
cols = empty map from hd -> list of values
queue = [(root, hd 0)]
while the queue is not empty:
    take (node, hd) from the front
    append node.value to cols[hd]
    if node has a left child:  add (left,  hd - 1) to the queue
    if node has a right child: add (right, hd + 1) to the queue
return cols[hd] for each hd in sorted(cols)

The Python solution

from collections import deque, defaultdict
 
def vertical_order(root):
    if not root:
        return []
    cols = defaultdict(list)
    queue = deque([(root, 0)])
    while queue:
        node, hd = queue.popleft()
        cols[hd].append(node.val)
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    return [cols[hd] for hd in sorted(cols)]

• cols is a defaultdict(list) mapping a horizontal distance → the values in that column.
• The queue stores pairs (node, hd), so each node carries its own column index.
• queue.popleft() makes this a true BFS — front of the queue first, level by level.
• cols[hd].append(node.val) drops the value into its column; BFS order keeps it top-to-bottom.
• A left child inherits hd - 1, a right child hd + 1 — that is the whole column rule.
• sorted(cols) puts the column keys in left-to-right order so the final list reads -2, -1, 0, +1, +2.

Complexity

We touch each node a constant number of times, so the traversal is O(n). The only sort is over the column keys, of which there are at most n. The map and queue together hold at most n entries, so extra space is O(n).

When this pattern shows up

Practice