Binary Tree Vertical Order Traversal

medium tree bfs hash map

Problem

Given a binary tree, return its vertical order traversal — columns left-to-right, nodes within a column in top-down then left-to-right order.

Inputroot = [3,9,20,null,null,15,7]

Output[[9],[3,15],[20],[7]]

Column −1: [9]; 0: [3,15]; 1: [20]; 2: [7].

tree (level-order, 'n' for null)

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

function verticalOrder(root) {
  const cols = new Map();
  const q = [[root, 0]];
  while (q.length) {
    const [node, c] = q.shift();
    if (!node) continue;
    if (!cols.has(c)) cols.set(c, []);
    cols.get(c).push(node.val);
    q.push([node.left, c - 1]);
    q.push([node.right, c + 1]);
  }
  return [...cols.entries()].sort((a, b) => a[0] - b[0]).map(e => e[1]);
}

class Solution {
    public List> verticalOrder(TreeNode root) {
        TreeMap> cols = new TreeMap<>();
        Deque q = new ArrayDeque<>();
        q.add(new Object[]{root, 0});
        while (!q.isEmpty()) {
            Object[] p = q.poll();
            TreeNode n = (TreeNode) p[0]; int c = (int) p[1];
            if (n == null) continue;
            cols.computeIfAbsent(c, k -> new ArrayList<>()).add(n.val);
            q.add(new Object[]{ n.left, c - 1 });
            q.add(new Object[]{ n.right, c + 1 });
        }
        return new ArrayList<>(cols.values());
    }
}

vector> verticalOrder(TreeNode* root) {
    map> cols;
    queue> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto [n, c] = q.front(); q.pop();
        if (!n) continue;
        cols[c].push_back(n->val);
        q.push({n->left, c - 1});
        q.push({n->right, c + 1});
    }
    vector> out;
    for (auto& [k, v] : cols) out.push_back(v);
    return out;
}

Explanation

Picture dropping each node into a vertical column. The root sits in column 0, going left subtracts 1 from the column and going right adds 1. The answer is just the columns read from leftmost to rightmost.

We run a BFS where each queue entry is a pair (node, column). As we pop a node, we append its value to the list for its column in a map cols, then enqueue its left child with c - 1 and right child with c + 1.

Using BFS (top-down, left-to-right) means each column's list naturally fills in the required order — nodes higher up come first, and same-row nodes go left to right. At the end we sort the column keys and output their lists in order.

Example: tree [3, 9, 20, null, null, 15, 7]. Node 3 is column 0, 9 is column -1, 20 is column 1, 15 is column 0, 7 is column 2. Grouped and sorted: [[9], [3, 15], [20], [7]].

Every node is enqueued once and sorting the few column keys is cheap, so the work is about O(n).

Time: O(n) Space: O(n)