Binary Tree Vertical Order Traversal

Table of Contents +

Most tree questions walk top to bottom. This one is different. It asks you to read the tree in columns, left to right, like reading words on a page. So the real test here is whether you can give each node a column number and then group nodes by that number. Once you see that trick, the rest is easy.

🎯 The Problem

You get a binary tree. Return the values column by column, from the leftmost column to the rightmost.

The rules:

A binary tree is a structure where each node has a value and up to two children.
Place the tree on a grid. The root sits at column 0.
Going left drops the column number by one. Going right raises it by one.
That number is the column index. Nodes with the same column belong to the same vertical line.
Inside one column, read the nodes from top to bottom.

Input:
        3
       / \
      9   8
     / \ / \
    4  0 1  7

Output: [[4], [9], [3, 0, 1], [8], [7]]

Explanation:
  Column -2 has 4
  Column -1 has 9
  Column  0 has 3, 0, 1
  Column  1 has 8
  Column  2 has 7

Here is the same tree drawn with each node’s column number marked next to it.

🐢 Approach 1: Walk, Tag, Then Sort (Brute Force)

The idea in one line: walk the tree once, tag every node with its column and depth, then sort everything.

The idea:

Walk the whole tree once.
Give every node its column number as you go.
Store each value with its column and its depth. Depth is how far down the node sits.
Then sort by column, and within a column by depth.

Why it is weak:

The final sort costs an extra O(n log n). That log n is the price of sorting.
A depth-first walk can produce same-column nodes in the wrong top-to-bottom order.
So you must track depth and sort by it. That is bookkeeping you can avoid.

Here is the tag-and-sort code:

from collections import defaultdict, deque
def vertical_order(root):
    if not root: return []
    cols = defaultdict(list); q = deque([(root, 0)])
    while q:
        node, col = q.popleft()
        cols[col].append(node.val)
        if node.left: q.append((node.left, col - 1))
        if node.right: q.append((node.right, col + 1))
    return [cols[c] for c in sorted(cols)]

⚡ Approach 2: BFS With Column Buckets (Best)

The idea in one line: read the tree level by level so each column fills top to bottom, with no sort.

The idea:

Read the tree level by level. That is BFS, short for breadth-first search.
BFS uses a queue, a line where the first item in is the first item out.
BFS visits top nodes before bottom ones.
So within any column, nodes come out top to bottom on their own. No depth sorting.

How it works:

Carry each node together with its column number in the queue.
For every node, put its value into a bucket for its column. A bucket is a list tied to one column.
The left child gets column minus one. The right child gets column plus one.
Track the smallest and largest column seen.
At the end, read the buckets from the smallest column to the largest.

Why it is fast:

Each node is visited once and there is no sort.
That is O(n), which beats the sort-based O(n log n).

This diagram shows the BFS queue handing out column numbers and dropping each value into its bucket.

Steps to Solve

If the tree is empty, return an empty list.
Make a map from column number to a list of values.
Put the root in a queue with column 0. Track the smallest and largest column.
While the queue is not empty, pop a node and its column.
Add the node value to the bucket for that column.
Push the left child with column minus one, and the right child with column plus one. Update the smallest and largest column.
Walk from the smallest column to the largest column and collect each bucket in order.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a dictionary of buckets and a deque, which is a fast double-ended queue, for BFS.

from collections import deque, defaultdict


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


def vertical_order(root):
    if not root:
        return []
    cols = defaultdict(list)          # column -> list of values
    queue = deque([(root, 0)])        # root sits at column 0
    min_col = max_col = 0
    while queue:
        node, col = queue.popleft()
        cols[col].append(node.val)    # drop value into its column bucket
        min_col = min(min_col, col)
        max_col = max(max_col, col)
        if node.left:
            queue.append((node.left, col - 1))   # left child: column - 1
        if node.right:
            queue.append((node.right, col + 1))  # right child: column + 1
    return [cols[c] for c in range(min_col, max_col + 1)]


root = Node(3)
root.left = Node(9)
root.right = Node(8)
root.left.left = Node(4)
root.left.right = Node(0)
root.right.left = Node(1)
root.right.right = Node(7)
print(vertical_order(root))

The output of the above code will be:

[[4], [9], [3, 0, 1], [8], [7]]

Let us walk the Python version line by line, because it shows the idea most clearly.

The line if not root: return [] handles the empty tree first. No tree means no columns. So return nothing.

The line cols = defaultdict(list) makes the column map. A defaultdict(list) gives back an empty list the first time you touch a new column. So you never have to check if a column exists. That keeps the code short.

The line queue = deque([(root, 0)]) seeds the BFS. We push a pair: the root node and its column 0. Every item in the queue carries both the node and where it sits.

The line node, col = queue.popleft() takes the next node from the front of the queue. popleft removes from the front, so the oldest item leaves first. That is what makes it BFS, top before bottom.

The line cols[col].append(node.val) drops this node’s value into its column bucket. Because BFS reads top rows first, values land in top-to-bottom order on their own. No depth sorting.

The lines updating min_col and max_col remember the leftmost and rightmost columns. We need them so the final read knows where to start and stop.

The two if lines push the children. Left child gets col - 1. Right child gets col + 1. That single rule is the whole secret of the problem.

The final line [cols[c] for c in range(min_col, max_col + 1)] reads the buckets from leftmost to rightmost. That produces the answer in correct column order.

⏱️ Time and Space Complexity

The recursive way visits every node once but then sorts them, so it pays an extra O(n log n). The BFS way visits every node once and never sorts, because the queue already gives top-to-bottom order and we track the column range. So BFS lands at a clean O(n). Both store every value, so both use O(n) memory.

Approach	Time Complexity	Space Complexity
Recursive walk then sort	O(n log n)	O(n)
BFS with column buckets	O(n)	O(n)

Tip

The key insight to say out loud is the column rule. Left subtracts one, right adds one. Once the interviewer hears that, they know you understand the structure of the problem.

🧩 Key Takeaways

✅ Give the root column 0, then left child is column minus one and right child is column plus one.
✅ Group node values into one bucket per column number.
✅ Use BFS so nodes in the same column come out top to bottom on their own.
✅ Track the smallest and largest column so you can read buckets in order without sorting.
✅ BFS gives O(n) time, which beats the sort-based O(n log n).

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Previous Serialize and Deserialize Binary Tree Next Binary Tree Zigzag Level Order Traversal

Binary Tree Vertical Order Traversal

Follow Us

Follow Us