Binary tree vertical order traversal

In this article

1. Before you start
2. Why interviewers ask this
3. Vertical order traversal from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

The problem exposes whether a candidate can invent a coordinate system and keep two orderings straight at once. Most people can walk a tree; fewer notice that "left to right" and "top to bottom" are two separate sort keys and that a plain recursive walk can produce the wrong order inside a column. A weak answer groups nodes by column but lists them in whatever order a depth-first walk reached them.

A strong answer states the ordering rule before coding, picks a breadth-first walk because it visits shallower nodes first, and names the cost of the alternative. The question also tests clarifying habits: whether you ask what happens on a tie, what an empty tree returns and whether the tree can be very deep. Those are the same habits the coding interviews hub treats as part of any solution.

Vertical order traversal from first principles

Vertical order traversal

Vertical order traversal is an ordering of a binary tree's nodes that groups them by column, from the leftmost column to the rightmost, and lists the nodes of one column from top to bottom.

Column index

A column index is an integer label given to a tree node that is 0 for the root, one lower for a left child than for its parent and one higher for a right child.

Breadth-first search

Breadth-first search (BFS) is a graph or tree walk that uses a queue to visit every node at one depth before any node at the next depth.

In plain words

Picture the tree drawn on paper with the root at the top. Now draw straight vertical lines through the page. Every node sits on exactly one line. The answer is what you read when you walk along the lines from the left edge to the right edge and read each line from top to bottom.

The drawing has one rule. A left child goes one line to the left of its parent. A right child goes one line to the right. That rule turns a picture into a number: the column index. The analogy breaks in one place: on paper two nodes can never land on the same spot, but in a real tree they can. That case gets its own section below.

Text description of the diagram

• The root is column 0, a left child is one column to the left and a right child one column to the right.
• The example tree has five columns, from minus 2 to 2.
• Reading the columns left to right gives 4, then 9 and 6, then 3, 15 and 5, then 20, then 7.

Step 1: Label every node with a column index

The first step gives each node a column index by starting the root at 0 and moving by one for every edge. The input is the root; the output is a pair of node and column for every node reached. A left child inherits its parent's column minus one and a right child inherits it plus one, so the index is computed from the parent in constant time and never needs a separate pass.

In the example tree above, the root 3 is column 0, its left child 9 is column -1, 9's left child 4 is column -2, and 4's right child 6 returns to column -1; 6's right child 5 lands in column 0.¹ Nothing else about the tree matters yet: the shape decides how many different columns exist, and the labels make that shape visible. You now know where every node belongs; the next step decides the order in which nodes reach their column.

Step 2: Visit nodes level by level with a queue

The second step walks the tree with a queue so that shallower nodes are always handled before deeper ones. The queue holds pairs of node and column; the walk removes the front pair, records it and adds the two children with their new columns. Python's documentation on collections says a deque supports appends and pops from either side "with approximately the same O(1) performance in either direction", and it warns that a plain list costs O(n) memory movement for pop(0).

A deque is therefore the right queue. Because the walk goes level by level, two nodes in the same column always arrive with the shallower one first, which is exactly the top-to-bottom rule. The output of this step is a stream of values in an order where depth never decreases.

Step 3: Drop each value into its column's list

The third step stores every visited value in a list kept under its column index in a hash map. The input is the stream from step 2 and the output is a map from column to the values seen in that column, in arrival order. A hash map read and write is constant time on average and linear in the worst case, per Python's time-complexity table, which is why the total stays linear in the number of nodes for ordinary inputs.

While inserting, the code also tracks the smallest and largest column index seen. Those two numbers are what step 4 needs, and tracking them costs two comparisons per node instead of a sort of the keys. The map is now complete: no value moves again after this step.

Step 4: Read the lists from the smallest column to the largest

The fourth step turns the map into the answer by reading the column indexes from the smallest to the largest seen. Counting from the minimum to the maximum visits every column once and keeps empty columns out of the picture, because a tree's column indexes form an unbroken range: every column between the leftmost and the rightmost holds at least one node.

The output is a list of lists. On the example tree the result is 4, then 9 and 6, then 3, 15 and 5, then 20, then 7.¹ The four steps are one loop and one loop over the keys; the diagram shows how they fit together, and the code section further down is the same four steps in about fifteen lines.

1 · Label2 · Visit3 · Bucket4 · Read outReplay

Step-by-step description

1. Root is column 0; left is minus one, right is plus one.
2. The queue pops 3, 9, 20, 4, 15, 7, 6, 5, one level at a time.
3. Each popped value joins its column's list; column 0 fills as 3, 15, 5.
4. Lists from column -2 to 2: [[4],[9,6],[3,15,5],[20],[7]].

• The queue holds pairs of node and column.
• The pop order is 3, 9, 20, 4, 15, 7, 6, 5.
• Reading the columns from -2 to 2 gives [[4], [9, 6], [3, 15, 5], [20], [7]].

What happens when two nodes share a row and a column?

Two nodes share a row and a column when they sit at the same depth and column index, under different parents. The problem statement must say how to order them, and two rules are common: keep them in left-to-right order of arrival, or sort them by value. The two classic problems differ here, as the solution notes show. walkccc.me's notes for LeetCode 314 (read 2026-10-24) use a plain breadth-first walk with no value sort, while its notes for LeetCode 987 (read 2026-10-24) keep a sorted set of row-and-value pairs for each column, so ties come out sorted by value.

A queue gives the first rule for free; the second needs a sort. On the tree with level order 1, 2, 3, null, 7, 4, the nodes 7 and 4 both sit in column 0 at depth 2: left-to-right order gives 1, 7, 4 for that column, and sorting by value gives 1, 4, 7.¹ Each answer is wrong under the other rule. Ask the interviewer and say the rule aloud before you code.

Worked example

Run the algorithm on the eight-node tree with level order 3, 9, 20, 4, null, 15, 7, null, 6, null, null, null, null, null, 5, where null marks a missing child. Node 5 is the right child of 6, which puts it in column 0 at depth 4, two levels below node 15. The code was executed, not hand-traced.¹

Reading columns -2 to 2 gives [[4], [9, 6], [3, 15, 5], [20], [7]], and the depth-first solution that sorts by column, depth and arrival order returns the identical result.¹

The last row is where the method earns its keep. A plain recursive walk that appends each value to its column on arrival goes down the left branch first, so it reaches 5 (depth 4) before it ever reaches 15 (depth 2) and returns [3, 5, 15] for column 0. The breadth-first walk handles every shallower node first, so it returns [3, 15, 5].¹ On the same tree without node 5 the two walks agree, which is why a small example can hide the bug.

The cost matters as much as the output. The script also counted work on four trees of about 1,000 nodes. Both methods visit every node once: 1,023 visits on a balanced tree of 1,023 nodes and 1,000 on each of the others. The sort-based method then makes extra key comparisons: 8,122 on the balanced tree, 999 on a left chain, 4,749 on a zigzag chain and 8,256 on a random tree.¹ Those counts are not a growth curve, because every tree has about the same size; they show how the comparisons depend on the shape.

The left chain needs only 999, one per neighbouring pair, because its records arrive in exactly reverse order (columns 0, -1, -2 and so on), and Python's time-complexity page notes in its footnotes that sorting is adaptive: input that is already sorted or reverse-sorted takes only O(n) comparisons. The same page lists the sort as O(n log n) in the worst case, and the balanced and random trees come close to it.

Text description of the diagram

• Both methods visit each node once: 1,023 visits on a balanced tree of 1,023 nodes and 1,000 on each tree of 1,000 nodes.
• The sort-based method then made 8,122 key comparisons on the balanced tree, 999 on a left chain, 4,749 on a zigzag chain and 8,256 on a random tree.

Here is the whole breadth-first solution in Python, using a defaultdict for the column map. It follows the four steps one to one.

from collections import deque, defaultdict

def vertical_order(root):
    if root is None:
        return []
    columns = defaultdict(list)          # step 3: column -> values
    queue = deque([(root, 0)])           # step 1: (node, column)
    low = high = 0
    while queue:                         # step 2: level by level
        node, col = queue.popleft()
        columns[col].append(node.val)
        low, high = min(low, col), max(high, 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(low, high + 1)]   # step 4

Time is linear in the number of nodes and space is linear too, for the queue, the map and the output; a published solution write-up states the same linear bounds for this approach.

Trade-offs and edge cases

The breadth-first solution is the default; the depth-first solution trades speed and safety for a simpler tie rule. A depth-first walk records the column, the depth and an arrival counter for every node and then sorts. That costs O(n log n) in the worst case instead of O(n), and the counts above show up to about 8,000 extra comparisons on 1,000 nodes. It also recurses once per tree level (see depth-first search), and Python's default recursion limit is 1,000 calls in the script's run, so a skewed tree of 1,000 nodes raises a RecursionError without raising the limit.¹ The breadth-first solution has no such limit because its queue lives on the heap.

Edge cases to name aloud: an empty tree returns an empty list; a single node returns one list; a tree that only goes left produces one column per node, which makes the output as long as the tree is tall (1,000 columns for the 1,000-node left chain, each holding one value).¹ A zigzag chain shows the opposite: two columns holding 500 values each.

What if the tree does not fit on one machine? This is our reasoning, not a published recipe. The column index is a natural partition key. Each worker walks its share of the tree and emits records of column, depth, arrival rank and value; records are routed so that every record of one column reaches the same shard; each shard sorts its records by depth and rank.

Because every step depends only on its input, a failed worker can be rerun on the same input and produce the same records, which is what makes the design tolerant of failures. The cost is a shuffle of all n records. For the larger system-design framing, see the system design hub and, for large-scale data pipelines, the data engineering hub.

How to answer it in an interview

The spoken structure is: define the column, name the walk and why it fits, state the cost, then ask about ties.

Common mistakes

"I will use a depth-first search with recursion." (wrong) A depth-first walk can reach a deeper node of a column before a shallower one from another branch (5 before 15 in the worked example), so the top-to-bottom order breaks unless you also sort by depth. (right) "A breadth-first search gives the order for free; with a depth-first search I must sort on depth."

"I will sort the map's keys at the end." (wrong) That adds an O(k log k) step for k columns that tracking the minimum and maximum avoids. (right) "The columns form an unbroken range, so I loop from the minimum to the maximum."

"Use a list as the queue." (wrong) Removing from the front of a list moves every other element, so each pop is O(n). (right) "I use a deque so that popping from the front is constant time."

"The tie rule does not matter." (wrong) It changes the output, as the 1, 7, 4 versus 1, 4, 7 example shows. (right) "I will confirm whether ties keep left-to-right order or sort by value."

Follow-up questions

How do you do vertical order traversal with a depth-first search?

Record the column, the depth and an arrival counter for every node during a recursive walk, sort the records by those three keys and group by column. The cost is O(n log n) for the sort, and deep trees need an explicit stack to avoid the recursion limit; Python's sorting guide notes sorts are stable, so equal keys keep their input order.

What if the tree is too large for one machine?

Partition by column: workers walk subtrees and emit column, depth, rank and value records, a shuffle sends one column to one shard, and each shard sorts its own records. A failed worker is rerun on its input and emits the same records.

What if nodes that share a row and column must be sorted by value?

Use the depth-first record approach with the value as the third sort key, or keep the breadth-first walk and sort each column's ties after it. On the tie example in this page the two rules give 1, 7, 4 and 1, 4, 7 for column 0.

What are the time and space complexity?

Time and space are both O(n) for the breadth-first solution, with the hash map assumed to run at its average constant-time cost; the sort-based variant takes O(n log n) time. The output alone holds n values.

Why use a queue instead of recursion?

A queue visits one depth fully before the next, which is the order the output needs inside a column. It also avoids call-stack growth on a deep or skewed tree.

For the neighbouring round formats, read the interview loops guide, the machine-learning coding round and the list of questions to ask the interviewer.

Sources

1. collections - Container datatypes (deque) — Python documentation, 24 Oct 2026
2. Time complexity of built-in types — Python documentation, 24 Oct 2026
3. Sorting Techniques (stability and Timsort) — Python documentation, 24 Oct 2026
4. 314. Binary Tree Vertical Order Traversal - solution notes — walkccc.me, 24 Oct 2026
5. 987. Vertical Order Traversal of a Binary Tree - solution notes — walkccc.me, 24 Oct 2026