Vertical order of a tree: A Sample Coding Interview Solution

The coding question

Given a binary tree, return its values in vertical order: column by column from left to right, and top to bottom within each column.

Ask a few questions first

Ask	What we'll assume
How are columns numbered?	The root is column 0. A left child is one column left, a right child is one column right.
Two nodes in the same row and column: which comes first?	Left to right, the order you'd see them in a level-by-level walk.
What should an empty tree return?	An empty list.
How big can the tree get?	Up to about 10,000 nodes.

A couple of examples

Input	Output
[3, 9, 20, null, null, 15, 7]	[[9], [3, 15], [20], [7]]
[3, 9, 8, 4, 0, 1, 7]	[[4], [9], [3, 0, 1], [8], [7]]
[] (empty tree)	[]

Start with brute force

Walk the tree any way you like and record (column, row, order seen) for each node. Then sort all of them and group by column.

Cost: O(n log n) time for the sort and O(n) space. It works, and it's a fine thing to say first, but the sort isn't needed.

A better way

A breadth-first walk visits rows from top to bottom, and left to right within a row. That's exactly the order we want inside each column, so if we append values as we visit them, each column comes out already sorted.

Group values in a hash map from column number to a list. Track the smallest and largest column as you go. At the end, read columns from smallest to largest, so there's no sort at all.

If the tree is empty, return an empty list.
Put (root, 0) in a queue.
Pop a node, append its value to its column's list, and update the smallest and largest column.
Push the left child with column - 1 and the right child with column + 1.
When the queue is empty, return the lists for every column from smallest to largest.

The code

solution.pypython

from collections import defaultdict, deque


class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def vertical_order(root):
    if root is None:
        return []
    columns = defaultdict(list)
    queue = deque([(root, 0)])
    lo = hi = 0
    while queue:
        node, col = queue.popleft()
        columns[col].append(node.val)
        lo = min(lo, col)
        hi = max(hi, col)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return [columns[c] for c in range(lo, hi + 1)]

	Cost	Why
Time	O(n)	Each node is visited once, and columns are read in order without sorting
Space	O(n)	The queue and the column lists

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

Empty tree: returns [].
Just a root: returns [[1]] for a root of 1.
A tree that only goes left, like 1 → 2 → 3 → 4: every node gets its own column, giving [[4], [3], [2], [1]].
Two nodes in the same row and column, like 0 and 1 in the second example: they come out left to right.

Common mistakes

Using a depth-first walk and appending as you go. DFS can reach a deep node in a column before a shallow one, so the top-to-bottom order breaks.
Sorting the column keys at the end when you could have tracked the min and max.
Mixing this up with the version that sorts ties by value. Ask which one they want.

Follow-up questions

What if nodes in the same row and column should be sorted by value?

Record (row, value) per column instead of just the value, and sort each column's list at the end. That's O(n log n).

Can you do it with DFS?

Yes, if you record the row too, then sort each column by row and keep the order seen for ties. It's more fiddly than BFS.

How would you return just the top view of the tree?

Same BFS, but only keep the first value you see in each column.

How the time adds up

Minutes	What you're doing
0–2	Clarify, especially the tie rule. Meta usually wants two problems in about 45 minutes, so you get about 20 for each
2–4	Brute force: walk, then sort
4–8	Explain why BFS order means no sort
8–15	Write the code
15–18	Walk through the second example, where the tie is
18–20	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Meta.