DSA Vertical Order Traversal

The problem

Vertical order traversal reads a binary tree column by column. Columns print from the leftmost to the rightmost. Inside one column, nodes print by row first and then by value.

The root sits in column 0 at row 0. A left child sits one column lower and one row deeper than its parent. A right child sits one column higher and one row deeper.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree_a = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
tree_b = TreeNode(1,
                  TreeNode(2, None, TreeNode(4)),
                  TreeNode(3, TreeNode(5)))

print("Tree A expected:", [(-1, [9]), (0, [3, 15]), (1, [20]), (2, [7])])
print("Tree B expected:", [(-1, [2]), (0, [1, 4, 5]), (1, [3])])

Tree B holds the tie that decides the ordering rule. Its nodes 4 and 5 share column 0 and row 2. The tie rule prints the smaller value first.

Intuition: group by column, then sort somehow

The first idea gives every node a column and a row, then groups nodes by column. Grouping alone leaves one question open. The order inside a column still needs a rule.

Sorting a column by value alone is the tempting shortcut. It fails whenever a deep small value shares a column with a shallow large one. Row must lead, and value may only break ties.

entries = [(0, 10), (2, 5)]
by_value = [v for row, v in sorted(entries, key=lambda e: e[1])]
by_row = [v for row, v in sorted(entries)]
print("column entries (row, value):", entries)
print("sorted by value only:", by_value)
print("sorted by row, then value:", by_row)

Value order places 5 above 10, although 5 sits two rows deeper. Row order keeps the reading top to bottom. The printed difference is the whole reason for the two-part sort key.

Brute force: scan the whole list for every column

The brute force first collects every node's column, row, and value in one flat list. It then finds the smallest and largest columns. For each column it scans the entire list again, gathering that column's entries and sorting them.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree_a = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
tree_b = TreeNode(1,
                  TreeNode(2, None, TreeNode(4)),
                  TreeNode(3, TreeNode(5)))

def collect(node, column, row, out):
    if node is None:
        return
    out.append((column, row, node.value))
    collect(node.left, column - 1, row + 1, out)
    collect(node.right, column + 1, row + 1, out)

def brute(root):
    entries = []
    collect(root, 0, 0, entries)
    scans = 0
    result = []
    low = min(c for c, r, v in entries)
    high = max(c for c, r, v in entries)
    for column in range(low, high + 1):
        scans += len(entries)
        here = sorted((r, v) for c, r, v in entries if c == column)
        if here:
            result.append((column, [v for r, v in here]))
    return result, scans

for label, tree in [("Tree A", tree_a), ("Tree B", tree_b)]:
    result, scans = brute(tree)
    print(label, "columns:", result, "list entries scanned:", scans)

The brute force answers correctly and pays a full scan per column. Wide trees hold many columns, so the repeated scanning grows with the tree's width. A single pass that files each node directly removes the repeat.

The optimal solution: breadth-first, filed by column

Breadth-first search visits nodes level by level, and carrying each node's column and row in the queue beside the node lets one pass file every node into its column. That one sentence is the whole method.

A map holds one list per column. After the pass, columns print in rising column order. Each column's entries sort by row, then by value, exactly as the problem states.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree_a = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
tree_b = TreeNode(1,
                  TreeNode(2, None, TreeNode(4)),
                  TreeNode(3, TreeNode(5)))
from collections import deque

def vertical_order(root):
    if root is None:
        return []
    columns = {}
    queue = deque([(root, 0, 0)])
    while queue:
        node, column, row = queue.popleft()
        columns.setdefault(column, []).append((row, node.value))
        if node.left is not None:
            queue.append((node.left, column - 1, row + 1))
        if node.right is not None:
            queue.append((node.right, column + 1, row + 1))
    result = []
    for column in sorted(columns):
        entries = sorted(columns[column])
        result.append((column, [value for row, value in entries]))
    return result

for label, tree in [("Tree A", tree_a), ("Tree B", tree_b)]:
    for column, values in vertical_order(tree):
        print(label, "column", column, ":", values)

Tree A spreads over four columns, with 3 above 15 in the middle one. Tree B places 4 before 5 in its middle column. The tie rule, not visit luck, decides that order, because the entries sort explicitly.

Walkthrough: Tree B through the queue

The queue starts with the root at column 0, row 0. Each step removes the front entry, files its value, and queues its children with their own coordinates. The printed state follows the map after each filing, with columns in rising order.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree_a = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
tree_b = TreeNode(1,
                  TreeNode(2, None, TreeNode(4)),
                  TreeNode(3, TreeNode(5)))

from collections import deque
columns = {}
queue = deque([(tree_b, 0, 0)])
while queue:
    node, column, row = queue.popleft()
    columns.setdefault(column, []).append((row, node.value))
    state = [(c, sorted(columns[c])) for c in sorted(columns)]
    print("file value", node.value, "at column", column, "row", row, "->", state)
    if node.left is not None:
        queue.append((node.left, column - 1, row + 1))
    if node.right is not None:
        queue.append((node.right, column + 1, row + 1))
print("final middle column:", [v for r, v in sorted(columns[0])])

Node 4 files into column 0 before node 5 arrives from the other subtree. Both carry row 2. The final sort reads the middle column as 1, 4, 5, with the tie settled by value.

Complexity

The breadth-first pass visits each node once, and sorting all column entries together costs O(n log n) in the worst case, so total time is O(n log n). The map and the queue together hold every node once, so space is O(n).

The brute force scans the full entry list once per column. A tree with w columns pays n times w scanned entries, before any sorting begins.

for n in [7, 15, 31, 63]:
    height = n.bit_length()
    columns = 2 * height - 1
    print("complete tree nodes", n, "- columns:", columns,
          " brute entries scanned:", n * columns, " one-pass visits:", n)

The scan count grows with both size and width. The one-pass visit count grows only with size. That difference is the saving, and it needs no timing to see.

Edge cases and pitfalls

A left-leaning tree drives its columns negative. Rising column order still starts at the most negative index. Code that assumes columns start at zero loses the whole left half.

Two nodes can share a column and a row only under different parents at the same depth. Dropping the value tiebreak makes their order depend on visit order. The stated rule removes that luck.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree_a = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
tree_b = TreeNode(1,
                  TreeNode(2, None, TreeNode(4)),
                  TreeNode(3, TreeNode(5)))
from collections import deque

def vertical_order(root):
    if root is None:
        return []
    columns = {}
    queue = deque([(root, 0, 0)])
    while queue:
        node, column, row = queue.popleft()
        columns.setdefault(column, []).append((row, node.value))
        if node.left is not None:
            queue.append((node.left, column - 1, row + 1))
        if node.right is not None:
            queue.append((node.right, column + 1, row + 1))
    result = []
    for column in sorted(columns):
        entries = sorted(columns[column])
        result.append((column, [value for row, value in entries]))
    return result

print("empty tree:", vertical_order(None))
print("single node:", vertical_order(TreeNode(8)))
skew = TreeNode(1, TreeNode(2, TreeNode(3)))
for column, values in vertical_order(skew):
    print("left skew column", column, ":", values)
for column, values in vertical_order(tree_b):
    if column == 0:
        print("tie column:", values)

The skew prints three columns in rising order, starting below zero. The empty tree returns an empty list rather than failing. Both behaviours come from the same code path as the main cases.