☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Vertical Order Traversal

Medium TUF ID 125 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Place a binary tree on a grid: the root is at (row 0, column 0), the left child of a node at (r, c) is at (r + 1, c - 1) and its right child at (r + 1, c + 1). The vertical order traversal lists the columns from the leftmost to the rightmost. Inside one column, nodes are listed from top to bottom (by row), and nodes that share both row and column are listed in increasing order of value. Return one list per column. An empty tree gives an empty list.

Constraints: 0 ≤ n ≤ 1000 nodes in the LeetCode version, values fit in an int. Columns can be negative.

Example 1

tree (level order) = [3, 9, 20, null, null, 15, 7]

     3              3 at (0, 0)
    / \             9 at (1, -1), 20 at (1, 1)
   9   20           15 at (2, 0), 7 at (2, 2)
      /  \
     15   7

answer = [[9], [3, 15], [20], [7]]     // columns -1, 0, 1, 2

Example 2

tree (level order) = [1, 2, 3, 4, 6, 5, 7]

        1
      /   \
     2     3
    / \   / \
   4   6 5   7

answer = [[4], [2], [1, 5, 6], [3], [7]]
// 6 (right child of 2) and 5 (left child of 3) both sit at (2, 0), so they are sorted: 5 before 6

So every node gets a key (column, row, value), and the answer is all nodes sorted by that key and then cut into groups of equal column. The two approaches below differ only in how they do the sorting: once at the end, or continuously in ordered maps. Both have to get the three-level tie-breaking exactly right, and that is where most wrong answers come from.

Approach 1: Collect triples, sort once

Intuition. Walk the tree with any traversal, passing each node’s row and column down to its children, and record a triple {col, row, value} per node. The traversal order is irrelevant, because a single sort by (col, row, value) puts everything in its final order. Then scan the sorted triples and start a new inner list whenever the column changes.

Algorithm.

  1. DFS from the root with (row 0, col 0); for each node add {col, row, val}; recurse left with (row + 1, col - 1) and right with (row + 1, col + 1).
  2. Sort the triples by column, then row, then value.
  3. Scan them in order. If the column differs from the previous one (or this is the first triple), start a new list. Append the value to the last list.
static List<List<Integer>> sortTriples(TreeNode root) {
    List<int[]> triples = new ArrayList<>();
    collect(root, 0, 0, triples);
    triples.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
            : a[1] != b[1] ? Integer.compare(a[1], b[1])
            : Integer.compare(a[2], b[2]));
    List<List<Integer>> out = new ArrayList<>();
    int prevCol = 0;
    for (int[] t : triples) {
        if (out.isEmpty() || t[0] != prevCol) {
            out.add(new ArrayList<>());          // a new column starts
            prevCol = t[0];
        }
        out.get(out.size() - 1).add(t[2]);
    }
    return out;
}

static void collect(TreeNode node, int row, int col, List<int[]> triples) {
    if (node == null) return;
    triples.add(new int[]{col, row, node.val});
    collect(node.left, row + 1, col - 1, triples);
    collect(node.right, row + 1, col + 1, triples);
}

Dry run on Example 2. The DFS records (0,0,1) (-1,1,2) (-2,2,4) (0,2,6) (1,1,3) (0,2,5) (2,2,7), as {col, row, val}. After sorting:

col row val action
-2 2 4 new column: [4]
-1 1 2 new column: [2]
0 0 1 new column: [1]
0 2 5 same column: [1, 5]
0 2 6 same column: [1, 5, 6]
1 1 3 new column: [3]
2 2 7 new column: [7]

Complexity. Time O(n log n), dominated by the sort; the walk and the grouping scan are O(n). Space O(n) for the triples, plus O(h) for the recursion.

The comparator uses Integer.compare at each level rather than subtraction such as a[0] - b[0]. Subtraction is a habit worth breaking: with values near the int limits it overflows and produces a comparator that is not even consistent.

Approach 2: BFS into nested ordered maps

Intuition. This is the approach taught in the sheet. Instead of sorting at the end, keep the data sorted as it arrives:

A TreeMap iterates its keys in increasing order, so walking the outer map gives columns left to right and walking an inner map gives rows top to bottom. The heap orders values that share a cell; polling it until empty yields them in increasing order. The traversal itself can be BFS or DFS, since the maps do all the ordering. BFS with a queue of (node, row, col) tuples is the usual choice and avoids recursion.

Algorithm.

  1. Enqueue (root, 0, 0) if the root exists.
  2. While the queue is not empty: poll (node, row, col), add node.val to map[col][row] (creating the inner map or heap on first use), enqueue the children with updated coordinates.
  3. For each column in increasing order, for each row in increasing order, poll that cell’s heap until empty into the column’s list.
static List<List<Integer>> treeMapBfs(TreeNode root) {
    TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>();
    Deque<Tuple> q = new ArrayDeque<>();
    if (root != null) q.add(new Tuple(root, 0, 0));
    while (!q.isEmpty()) {
        Tuple t = q.poll();
        map.computeIfAbsent(t.col, k -> new TreeMap<>())
           .computeIfAbsent(t.row, k -> new PriorityQueue<>())
           .add(t.node.val);
        if (t.node.left != null) q.add(new Tuple(t.node.left, t.row + 1, t.col - 1));
        if (t.node.right != null) q.add(new Tuple(t.node.right, t.row + 1, t.col + 1));
    }
    List<List<Integer>> out = new ArrayList<>();
    for (TreeMap<Integer, PriorityQueue<Integer>> rows : map.values()) {
        List<Integer> column = new ArrayList<>();
        for (PriorityQueue<Integer> cell : rows.values()) {
            while (!cell.isEmpty()) column.add(cell.poll());
        }
        out.add(column);
    }
    return out;
}

computeIfAbsent creates the inner TreeMap or the PriorityQueue only when a column or cell is seen for the first time, and returns the existing one otherwise, so the insertion is a single chained expression.

Complexity. Time O(n log n): each insertion costs O(log n) in the two maps and in the heap, and each heap poll costs O(log n). Space O(n) for the maps and the queue.

Choosing between them

Both approaches are O(n log n) and give identical results; the Java file compares them on 300 seeded random trees whose values are drawn from a small range so that many cells hold duplicates. The triple sort is shorter and easier to get right, since the tie-breaking rule lives in one comparator. The nested maps are what you want when results must be available column by column or when the tree arrives incrementally. Neither can beat O(n log n) in general, because the output requires sorting values inside cells.

Edge cases and pitfalls