Binary Tree Vertical Ordering

Description

Vertical ordering reads a tree in columns, as if it were drawn on paper and sliced vertically. Every node gets two coordinates. Its column is one left of its parent for a left child and one right for a right child. Its row is its level. The answer groups nodes by column, from left to right, and top to bottom within each column. Top and bottom views keep one node per column; vertical order keeps them all.

We'll go from simple to more technical:

1. The pattern: BFS assigning columns and rows, then grouping.
2. A second flavor: when order inside a column doesn't matter (vertical sums).
3. Where giving every node a 2D position is needed.
4. The coordinate bugs, tie-breaking, and map ordering.

The approach

The root is in column 0, row 0. A left child sits one column to the left of its parent, a right child one column to the right, and both one row down. Walk the tree with BFS, give every node its column and row, and add it to a list for its column.

Read left to right, the columns are [1], [3], [5, 4], [9] and [12]. The top view keeps the first node in each column: 1, 3, 5, 9, 12. The bottom view keeps the last: 1, 3, 4, 9, 12.

// BFS carrying (node, hd, level); a TreeMap keeps the columns sorted by hd
TreeMap<Integer, List<int[]>> columns = new TreeMap<>();      // hd -> list of {level, val}
Queue<Object[]> queue = new ArrayDeque<>();
if (root != null) queue.offer(new Object[]{root, 0, 0});
while (!queue.isEmpty()) {
    Object[] e = queue.poll();
    TreeNode node = (TreeNode) e[0];
    int hd = (int) e[1], level = (int) e[2];
    columns.computeIfAbsent(hd, k -> new ArrayList<>()).add(new int[]{level, node.val});
    if (node.left != null)  queue.offer(new Object[]{node.left,  hd - 1, level + 1});
    if (node.right != null) queue.offer(new Object[]{node.right, hd + 1, level + 1});
}
for (List<int[]> col : columns.values())
    col.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));  // level, then value

from collections import defaultdict, deque

# BFS carrying (node, hd, level); Python has no TreeMap - sort the column keys at the end
columns = defaultdict(list)                     # hd -> list of (level, val)
queue = deque([(root, 0, 0)] if root else [])
while queue:
    node, hd, level = queue.popleft()
    columns[hd].append((level, node.val))
    if node.left:
        queue.append((node.left, hd - 1, level + 1))
    if node.right:
        queue.append((node.right, hd + 1, level + 1))
result = [[val for _, val in sorted(columns[hd])] for hd in sorted(columns)]   # level, then value

hd stands for horizontal distance, the column. The TreeMap returns the columns left to right. BFS visits level by level, so each column's list is already top to bottom. The sort is there for ties: two nodes can share a column and a row, and the problem then orders them by value. For the top view, keep only the first node per column (putIfAbsent); for the bottom view, the last (put, overwriting).

A second flavor: when order inside a column doesn't matter

The vertical sum of each column doesn't depend on the order its nodes arrive in. So there's nothing to sort, and no need for a TreeMap either. In the tree above, the sums are 1, 3, 9, 9 and 12 (column 0 adds 5 and 4).

Map<Integer, Long> sums = new HashMap<>();
int minHd = 0, maxHd = 0;
void walk(TreeNode node, int hd) {
    if (node == null) return;
    sums.merge(hd, (long) node.val, Long::sum);
    minHd = Math.min(minHd, hd);
    maxHd = Math.max(maxHd, hd);
    walk(node.left, hd - 1);
    walk(node.right, hd + 1);
}
// then emit sums.get(hd) for hd = minHd .. maxHd

def vertical_sum(root: TreeNode) -> list[int]:
    sums = {}
    lo = hi = 0

    def walk(node: TreeNode | None, hd: int) -> None:
        nonlocal lo, hi
        if node is None:
            return
        sums[hd] = sums.get(hd, 0) + node.val
        lo, hi = min(lo, hd), max(hi, hd)
        walk(node.left, hd - 1)
        walk(node.right, hd + 1)

    walk(root, 0)
    return [sums[hd] for hd in range(lo, hi + 1)]   # every column in lo..hi is non-empty

Any traversal works, even DFS. To list the columns in order, count from the smallest column to the largest. Every column in that range has a node, because each edge moves exactly one column. That makes it O(n) instead of O(n log n).

Where you'll see it

Drawing a tree as a diagram, such as a family tree or a syntax tree in a debugger, needs these columns before anything can be placed.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. In [1, 2, 3, 4, 5, 6, 7], which nodes are in column 0, and why do two of them need a tie-break?

2. Why can the vertical sum use a HashMap and skip sorting, when vertical order can't?

3. A top view keeps the first node a preorder DFS reaches in each column. Give a tree where that's wrong.

Key takeaways

• Each node needs two coordinates: its column and its row.
• A TreeMap by column gives left-to-right order, and BFS gives top-to-bottom order. Sort only for nodes sharing a column and a row.
• Top and bottom views keep one node per column; vertical order keeps them all.
• A column sum needs no sorting: a HashMap plus the smallest and largest column is O(n).
• Never read columns straight out of a HashMap, and never treat DFS order as top to bottom.