LeetCode 314: Binary Tree Vertical Order Traversal

Problem Restatement

We are given the root of a binary tree.

Return the vertical order traversal of the tree’s node values.

Vertical order means:

1. Group nodes by column.
2. Output columns from left to right.
3. Inside each column, output nodes from top to bottom.
4. If two nodes have the same row and column, output the left node before the right node.

The root starts at column 0.

For any node:

The official statement asks for vertical order traversal from top to bottom, column by column, with left-to-right ordering when two nodes share the same row and column.

Input and Output

Function shape:

def verticalOrder(root: Optional[TreeNode]) -> list[list[int]]:
    ...

Examples

Example 1:

        3
       / \
      9   20
         /  \
        15   7

Column assignment:

Output:

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

Example 2:

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

Columns:

Output:

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

Notice column 0.

Nodes 0 and 1 are on the same row and same column. Since 0 comes from the left side and 1 comes from the right side, 0 appears first.

First Thought: DFS With Sorting

One possible solution is:

1. Traverse the tree.
2. Record each node as (column, row, order, value).
3. Sort by column, then row, then order.
4. Group by column.

This works, but sorting adds extra complexity.

There is a cleaner approach because the required order inside each column is top to bottom, and ties follow left-to-right tree order.

That is exactly what BFS gives us.

Key Insight

Use BFS level-order traversal.

BFS visits nodes by row from top to bottom.

If we push the left child before the right child, then nodes on the same row are visited from left to right.

So if we append each visited node into its column bucket during BFS, each bucket naturally has the correct order.

We only need to track the column index of each node.

Algorithm

If root is None, return an empty list.

Otherwise:

1. Create a dictionary:

   column_map = defaultdict(list)
2. Create a queue containing:

   (root, 0)
3. Track the smallest and largest column seen.
4. While the queue is not empty:
   • Pop (node, col).
   • Append node.val to column_map[col].
   • If node.left exists, push (node.left, col - 1).
   • If node.right exists, push (node.right, col + 1).
5. Return buckets from min_col through max_col.

Correctness

BFS processes nodes level by level. Therefore, when a value is appended to a column bucket, all nodes above it have already been processed.

Within the same level, BFS processes nodes from left to right because we enqueue the left child before the right child for every node. Therefore, if two nodes share the same row and column, the left-side node is appended first.

Each node is assigned the correct column because the root starts at column 0, every left edge subtracts 1, and every right edge adds 1.

The dictionary groups exactly the nodes with equal column indices. Returning columns from min_col to max_col outputs them from left to right.

Therefore, the algorithm returns the required vertical order traversal.

Complexity

n is the number of nodes in the tree.

Implementation

from collections import defaultdict, deque
from typing import Optional

class TreeNode:
    def __init__(
        self,
        val: int = 0,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def verticalOrder(
        self,
        root: Optional[TreeNode],
    ) -> list[list[int]]:

        if root is None:
            return []

        column_map = defaultdict(list)
        queue = deque([(root, 0)])

        min_col = 0
        max_col = 0

        while queue:
            node, col = queue.popleft()

            column_map[col].append(node.val)

            min_col = min(min_col, col)
            max_col = max(max_col, col)

            if node.left:
                queue.append((node.left, col - 1))

            if node.right:
                queue.append((node.right, col + 1))

        return [
            column_map[col]
            for col in range(min_col, max_col + 1)
        ]

Code Explanation

We handle the empty tree first.

if root is None:
    return []

The column map stores one list per vertical column.

column_map = defaultdict(list)

The queue stores each node with its column.

queue = deque([(root, 0)])

The root is at column 0.

We also track the leftmost and rightmost columns.

min_col = 0
max_col = 0

During BFS:

node, col = queue.popleft()

Append the node value to its column.

column_map[col].append(node.val)

Update boundaries.

min_col = min(min_col, col)
max_col = max(max_col, col)

The left child goes one column left.

if node.left:
    queue.append((node.left, col - 1))

The right child goes one column right.

if node.right:
    queue.append((node.right, col + 1))

Finally, build the answer from leftmost column to rightmost column.

return [
    column_map[col]
    for col in range(min_col, max_col + 1)
]

Testing

def run_tests():
    s = Solution()

    root1 = TreeNode(
        3,
        TreeNode(9),
        TreeNode(
            20,
            TreeNode(15),
            TreeNode(7),
        ),
    )

    assert s.verticalOrder(root1) == [
        [9],
        [3, 15],
        [20],
        [7],
    ]

    root2 = TreeNode(
        3,
        TreeNode(
            9,
            TreeNode(4),
            TreeNode(0),
        ),
        TreeNode(
            8,
            TreeNode(1),
            TreeNode(7),
        ),
    )

    assert s.verticalOrder(root2) == [
        [4],
        [9],
        [3, 0, 1],
        [8],
        [7],
    ]

    assert s.verticalOrder(None) == []

    single = TreeNode(1)
    assert s.verticalOrder(single) == [[1]]

    left_chain = TreeNode(
        1,
        TreeNode(
            2,
            TreeNode(3),
        ),
    )
    assert s.verticalOrder(left_chain) == [[3], [2], [1]]

    right_chain = TreeNode(
        1,
        None,
        TreeNode(
            2,
            None,
            TreeNode(3),
        ),
    )
    assert s.verticalOrder(right_chain) == [[1], [2], [3]]

    print("all tests passed")

run_tests()

Test meaning: