Vertical Order Traversal of a Binary Tree: BFS With Columns

Most tree traversals read a tree top to bottom or level by level. Vertical order reads it in columns, left to right, as if you had drawn the tree on graph paper and read down each strip. The code is a small change to level-order traversal; the interesting part is being precise about what order the nodes inside one column should come out in.

The problem it solves

Given a binary tree, return its values grouped by column, from the leftmost column to the rightmost. For this tree:

        3
      /   \
     9     20
    / \   /  \
   4   5 6    7

the answer is [[4], [9], [3, 5, 6], [20], [7]]. The middle column holds the root and two grandchildren from different subtrees, 5 under 9 and 6 under 20, because both sit directly below the root on paper.

The intuition

Give every node an x-coordinate. The root is column 0; a left child is its parent's column minus one; a right child is plus one. That single number, carried down as you traverse, is enough to place every node horizontally. Grouping by it is a dictionary from column to list.

The remaining question is order within a column. The common version wants top to bottom, and for nodes on the same row, left to right. Breadth-first search produces exactly that for free: it finishes each row before starting the next, and within a row it visits nodes left to right. A depth-first walk would finish the entire left subtree first and could append a deep node before a shallower one in the same column.

Finally, the columns come out in discovery order, not left to right. Either sort the keys at the end, or, since columns are consecutive integers, track the smallest and largest column seen and read the range directly.

There is a stricter variant where two nodes on the same row and same column must be ordered by value instead of left to right. In the tree above, 5 and 6 are exactly such a pair. That variant needs row numbers too, and a sort.

Watch it run

The animation hangs a five-node tree on a grid, root at column 0. BFS places 9 at column -1, 20 at column 1, then 15 at column 0 and 7 at column 2. Then it reads the columns left to right: [9], then [3, 15], two nodes from different branches of the tree, then [20] and [7].

The code

BFS with a column range instead of a sort:

from collections import defaultdict, deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def vertical_order(root):
    """Columns left to right; inside a column, top to bottom, then left to right."""
    if root is None:
        return []
    cols, q = defaultdict(list), deque([(root, 0)])
    lo = hi = 0                              # column range, so no sort is needed
    while q:
        node, c = q.popleft()                # BFS: shallower nodes come out first
        cols[c].append(node.val)
        lo, hi = min(lo, c), max(hi, c)
        if node.left:
            q.append((node.left, c - 1))
        if node.right:
            q.append((node.right, c + 1))
    return [cols[c] for c in range(lo, hi + 1)]

tree = Node(3, Node(9, Node(4), Node(5)), Node(20, Node(6), Node(7)))
print(vertical_order(tree))                  # [[4], [9], [3, 5, 6], [20], [7]]

The stricter variant collects (column, row, value) for every node and sorts the triples, so ties on the same row and column fall back to value:

def vertical_traversal_sorted(root):
    cells = []
    def walk(node, row, col):
        if node:
            cells.append((col, row, node.val))
            walk(node.left, row + 1, col - 1)
            walk(node.right, row + 1, col + 1)
    walk(root, 0, 0)
    cells.sort()                             # column, then row, then value
    out, last = [], None
    for col, row, val in cells:
        if col != last:
            out.append([])
            last = col
        out[-1].append(val)
    return out

tie = Node(1, Node(2, Node(4), Node(6)), Node(3, Node(5), Node(7)))
print(vertical_order(tie))                   # [[4], [2], [1, 6, 5], [3], [7]]
print(vertical_traversal_sorted(tie))        # [[4], [2], [1, 5, 6], [3], [7]]

Both against independent references on 1,000 random trees with repeated values. The first reference takes coordinates from a depth-first walk and stable-sorts them by column and row; preorder visits nodes of equal depth left to right, which is the order BFS uses. The second rebuilds the rows level by level:

import random

def random_tree(n):
    if n == 0:
        return None
    left = random.randint(0, n - 1)
    return Node(random.randint(0, 9), random_tree(left), random_tree(n - 1 - left))

def reference(root):
    cells = []
    def walk(node, row, col):
        if node:
            cells.append((col, row, node.val))
            walk(node.left, row + 1, col - 1)
            walk(node.right, row + 1, col + 1)
    walk(root, 0, 0)
    cells.sort(key=lambda t: (t[0], t[1]))   # stable: ties keep left-to-right order
    groups = defaultdict(list)
    for col, row, val in cells:
        groups[col].append(val)
    return [groups[c] for c in sorted(groups)]

def reference_sorted(root):
    groups, level, row = defaultdict(list), ([(root, 0)] if root else []), 0
    while level:
        for node, c in level:
            groups[c].append((row, node.val))
        level = [(kid, c + d) for node, c in level
                 for kid, d in ((node.left, -1), (node.right, 1)) if kid]
        row += 1
    return [[v for _, v in sorted(groups[c])] for c in sorted(groups)]

random.seed(15)
ok = True
for _ in range(1000):
    root = random_tree(random.randint(0, 15))
    ok &= vertical_order(root) == reference(root)
    ok &= vertical_traversal_sorted(root) == reference_sorted(root)
print(ok)                                    # True

The complexity

• BFS version: every node is enqueued and dequeued once, O(n) time. The dictionary and the queue hold at most n entries, O(n) space. Reading the column range costs O(w) for w columns, and w is at most n.
• Sorting the keys instead of tracking the range adds O(w log w), still fine but unnecessary.
• Sorted-ties variant: collecting is O(n), and sorting all the triples is O(n log n), which dominates.

Where it goes wrong

• Using DFS for the common version. A deep node in the left subtree can be appended before a shallower node from the right subtree in the same column. Either use BFS or record rows and sort by them.
• Forgetting the columns are unordered. Iterating the dictionary returns columns in discovery order, root column first.
• Mixing up the two variants. For the tree above, the common version gives [3, 5, 6] in the middle column; with a tie like 6 left of 5 on one row, only the sorted variant reorders them. Ask which one is wanted.
• The empty tree. Return [] before touching root.val.

How to say it in an interview

"I give every node a column: root zero, left child minus one, right child plus one. I traverse breadth-first with (node, column) pairs in the queue, appending each value to a dictionary keyed by column. BFS guarantees top-to-bottom order inside each column, and left to right for nodes on the same row. I track the minimum and maximum column, so I can output the range without sorting. That's O(n) time and space. If same-row, same-column ties must be sorted by value, I collect (column, row, value) triples and sort them, O(n log n)."

The queue-driven walk underneath is the one in binary tree level-order traversal, and the coordinate idea starts from tree traversals.