Coding · Trees
Binary Tree Vertical Order Traversal
- Reported in several places
- Medium
- E4 and E5
- 4 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
A binary tree of up to 10,000 nodes is given in level-order form, with null for a missing child. Give every node a column: the root is column 0, a left child sits one column left of its parent and a right child one column right. Return the values grouped by column from left to right, listing each column top to bottom and, within one row, left to right. For example, [3,9,20,null,null,15,7] gives [[9],[3,15],[20],[7]].
Restated in our own words, not a quote from Meta or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: when two nodes share both a row and a column, what is the order? I will assume left to right, as they appear on the page, not sorted by value. Is the tree given as a level-order array with null for gaps? Can it be empty? Can values repeat or be negative? Do I return a list of lists, one per column? How many nodes are there, and how deep can the tree be?
Assumptions I would state: level-order input, an empty tree returns an empty list, values are arbitrary integers, up to 10,000 nodes, and the output has one list per column, left column first.
Brute force
Say the obvious answer and why it is too slow.
The direct way is to walk the tree once to find the smallest and largest column, then for each column from left to right walk the whole tree again, in level order, collecting the nodes that sit in that column. It is simple and the order inside each column comes out right.
The cost is one full traversal per column. The number of columns can be as large as n, for example in a tree where every node has only a right child, so the total is O(n × width), which is O(n²) in the worst case. At 10,000 nodes that is 100 million node visits to produce 10,000 values. A second option, recording (column, depth, position) for every node and sorting, is O(n log n) and acceptable, but it needs extra bookkeeping to break ties. A single pass can do better.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n × width), O(n²) worst case
- Time
- O(n) average, Map operations O(1)
- Space
- O(n)
The pattern is BFS with a hash map from column to list. Run a level-order traversal and put each node's column number in the queue next to it: the root has 0, a left child gets parent - 1, a right child gets parent + 1. When a node is dequeued, append its value to the list for its column in a Map.
Why does this give the right order with no sorting? A level-order traversal visits nodes top to bottom, and inside one level, left to right. So when node X is dequeued, every node above it and every node on its row to its left has already been dequeued. Each column's list is therefore appended to in exactly the order the problem asks for. This is why BFS is the right tool. A depth-first walk would reach a deep node in some column before a shallower node of that column on a different branch, and the lists would come out in the wrong order.
The columns are also consecutive: a child's column differs from its parent's by exactly one, so there are no empty columns between the smallest and the largest. I track the minimum and maximum column while traversing, and at the end read the Map for each column from the minimum to the maximum. No sorting of keys is needed.
One implementation detail: I use an array as the queue with a moving head index, since Array.prototype.shift can cost O(n) per call. Map lookups are O(1) on average.
Walk it through
A dry run on the example, step by step.
| Step | Node | Column | Column list after | Columns seen |
|---|---|---|---|---|
| 1 | 3 | 0 | 0: [3] | 0 to 0 |
| 2 | 9 | -1 | -1: [9] | -1 to 0 |
| 3 | 20 | 1 | 1: [20] | -1 to 1 |
| 4 | 15 | 0 | 0: [3,15] | -1 to 1 |
| 5 | 7 | 2 | 2: [7] | -1 to 2 |
| 6 | read out | -1 to 2 | [[9],[3,15],[20],[7]] | done |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take [3,9,20,null,null,15,7]. The root 3 has children 9 and 20; 20 has children 15 and 7. Breadth-first order is 3, 9, 20, 15, 7, and the table lists each visit.
The root goes into column 0. Node 9 is its left child, so column -1. Node 20 is its right child, column 1. Node 15 is the left child of 20, so column 1 - 1 = 0, and it is appended after 3 in column 0. Node 7 is the right child of 20, column 2. The range of columns seen grows from 0..0 to -1..2. Reading the map from column -1 to column 2 gives [9], [3,15], [20], [7], which is the answer.
The code
Runnable JavaScript, checked against test cases.
function verticalOrder(values) {
if (values.length === 0 || values[0] === null) return [];
const columns = new Map();
const queue = [[buildTree(values), 0]];
let leftmost = 0;
let rightmost = 0;
for (let head = 0; head < queue.length; head++) {
const [node, column] = queue[head];
if (!columns.has(column)) columns.set(column, []);
columns.get(column).push(node.val);
leftmost = Math.min(leftmost, column);
rightmost = Math.max(rightmost, column);
if (node.left) queue.push([node.left, column - 1]);
if (node.right) queue.push([node.right, column + 1]);
}
const result = [];
for (let column = leftmost; column <= rightmost; column++) {
result.push(columns.get(column));
}
return result;
}
function buildTree(values) {
const root = { val: values[0], left: null, right: null };
const waiting = [root];
let next = 1;
for (let head = 0; head < waiting.length && next < values.length; head++) {
for (const side of ["left", "right"]) {
if (next >= values.length) break;
const value = values[next++];
if (value === null) continue;
waiting[head][side] = { val: value, left: null, right: null };
waiting.push(waiting[head][side]);
}
}
return root;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty tree: an empty array, or one whose first entry is null, returns an empty list before any tree is built.
- Single node: one column holding one value.
- Right-only or left-only chains: each node lands in a new column, so every list has one value, ordered by direction.
- Same row, same column: a left subtree's right child and a right subtree's left child meet at the same column and row. BFS order puts the left one first.
- Null gaps in the input: a null consumes one slot and gets no children, which is how level-order arrays work.
- Negative columns: a Map takes negative keys without trouble.
Follow-ups to expect
Where the interviewer pushes next.
- What changes if nodes in the same row and column must be ordered by value instead of left to right?
- Can DFS solve it if you also store the depth of each node, and what does that cost?
- How would you print only the top view of the tree using the same column idea?
- Why does a BFS version avoid the recursion limit that a DFS version could hit on a deep tree?
- How would you adapt it to return the sum of each column instead of the values?
Where candidates slip
The mistakes this problem punishes.
The most common wrong answer is a DFS: it visits the whole left subtree first, so a deep left node can be appended to a column before a shallower node from the right branch, and the top-to-bottom order is broken.
- Keying a plain object by column and expecting numeric order. Negative keys keep insertion order, not numeric order, so track min and max instead.
- Using
queue.shift()in a loop, which can turn the traversal quadratic. - Pushing null children into the queue and then reading a value from null.
- Sorting ties by value, which solves a different problem.
- Forgetting the empty tree.
- Building the tree wrongly from the array, for example by treating it as a heap with children at 2i + 1 and 2i + 2, which is not how nulls are encoded.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.