#133

Binary Tree Vertical Order Traversal

medium

hash-tabletreedepth-first-searchbreadth-first-searchbinary-tree

Given the root of a binary tree, return its vertical order traversal — the node values grouped by column, from the leftmost column to the rightmost.

Assign the root column 0; a left child is one column to the left (col - 1) and a right child one column to the right (col + 1). Within a column, list nodes top to bottom; when two nodes share a column and a row, list them left to right (i.e. in the order a level-order scan reaches them).

The tree is given as a level-order array where null marks a missing child: [3, 9, 20, null, null, 15, 7].

Example

Input: root = [3,9,20,null,null,15,7]9315207

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

Columns -1..2: [9], then root 3 with 15 (both at col 0), then 20, then 7.

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Intuition

Assign the root column 0; a left child sits one column left (col - 1), a right child one column right (col + 1). The output groups node values by column, left to right, and within a column lists them top to bottom. A direct approach does a DFS recording each node's (column, row), then sorts everything into buckets at the end.

function verticalOrder(root) {
  const seen = [];
  // Record every node with its column and depth (row).
  const dfs = (node, col, row) => {
    if (!node) return;
    seen.push({ col, row, val: node.val });
    dfs(node.left, col - 1, row + 1);
    dfs(node.right, col + 1, row + 1);
  };
  dfs(root, 0, 0);
  // Group by column; within a column sort by row, then by insertion order.
  const byCol = new Map();
  for (const { col, row, val } of seen) {
    if (!byCol.has(col)) byCol.set(col, []);
    byCol.get(col).push({ row, val });
  }
  return [...byCol.keys()].sort((a, b) => a - b).map((col) =>
    byCol.get(col).sort((a, b) => a.row - b.row).map((e) => e.val));
}

Brute force — DFS collecting (col, row, val), then sort each column by row: O(n log n).

This works but the per-column sort makes it O(n log n), and a DFS visits a same-column node out of top-to-bottom order, which is why the sort was needed at all. Can we do better?

The key observation: the required within-column order — top to bottom, then left to right on a tie — is exactly the order a breadth-first traversal visits nodes. So if we BFS and carry each node's column index, appending into per-column buckets, every bucket comes out already correct. No sorting, just a final read from the smallest column to the largest. This is the level-order / queue pattern with an extra piece of state riding along.

Tracing [3, 9, 20, null, null, 15, 7]. BFS visits 3 (col 0), 9 (col -1), 20 (col 1), 15 (col 0), 7 (col 2). The lane below is the BFS visit order; each action shows which column bucket the value drops into:

BFS visit order — each node dropped into its column bucket

bfs↓

3 → col 0

Root enters column 0. Queue its children with cols -1 and +1.

bfs↓

9 → col -1

Left child of 3: column -1, the leftmost so far.

bfs↓

20 → col 1

Right child of 3: column +1. Its children will be cols 0 and 2.

bfs↓

15 → col 0

15 shares column 0 with the root — and BFS reaches it after 3, so it lands below 3 in the bucket.

bfs↓

7 → col 2

Buckets: col -1=[9], col 0=[3,15], col 1=[20], col 2=[7] → [[9],[3,15],[20],[7]].

Optimization

BFS with a column index

The within-column ordering is top to bottom, then left to right — exactly the order a breadth-first scan visits nodes. So do a BFS, carrying each node's column index alongside it, and append values into per-column buckets. BFS guarantees a node enqueued earlier (higher up, or further left on the same row) lands in its bucket first, so no per-bucket sorting is needed.

After the scan, read the buckets out from the minimum column to the maximum.

O(n) time, O(n) space for the queue and buckets.

function verticalOrder(root) {
  if (!root) return [];
  const columns = new Map();          // col index -> values, in BFS order
  let minCol = 0;
  let maxCol = 0;
  // Queue holds [node, column]; BFS preserves the top-to-bottom, left-to-right order.
  const queue = [[root, 0]];
  while (queue.length) {
    const [node, col] = queue.shift();
    if (!columns.has(col)) columns.set(col, []);
    columns.get(col).push(node.val);
    minCol = Math.min(minCol, col);
    maxCol = Math.max(maxCol, col);
    if (node.left) queue.push([node.left, col - 1]);
    if (node.right) queue.push([node.right, col + 1]);
  }
  // Read buckets left to right.
  const result = [];
  for (let col = minCol; col <= maxCol; col++) result.push(columns.get(col));
  return result;
}

Complexity analysis

Time complexity: O(n). Here's why:

The BFS visits each of the n nodes once, doing O(1) work (a map lookup and an append).
Reading the buckets out spans c columns where c ≤ n.

So O(n) — no per-column sort is needed, because BFS already delivers each column in the required order.

Space complexity: O(n). Here's why:

The queue and the column buckets together hold every node — O(n).

The output array also holds n values, but it's the unavoidable result; the extra working space is O(n).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
root = []null	[]	Empty tree — no columns.
root = [9]9	[[9]]	Single node sits alone in column 0.
root = [5,6,null,7]765	[[7],[6],[5]]	A left spine spreads one column further left at each step.
root = [2,4,6,8,10,12,14]8410212614	[[8],[4],[2,10,12],[6],[14]]	Column 0 collects the root then both inner grandchildren, in BFS order.
root = [0,-5,5]-505	[[-5],[0],[5]]	Negative values are grouped by column, not by magnitude.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor