Vertical Order Traversal of Binary Tree

Vertical order traversal groups tree nodes by their horizontal column position. Imagine vertical lines drawn through the tree — each line captures a “column” of nodes. This perspective unlocks several popular interview problems: top view, bottom view, and vertical sums.

The column concept

Assign column indices to nodes:

• The root is at column 0
• A left child is at parent_column - 1
• A right child is at parent_column + 1

Column:   -2  -1   0   1   2
               2
              / \
             1   3
            /   / \
           0   2   4

For the tree:

         1  (col 0)
        / \
       2    3  (col -1, col 1)
      / \    \
     4   5    7  (col -2, col 0, col 2)

Column -2: [4], Column -1: [2], Column 0: [1, 5], Column 1: [3], Column 2: [7]

TreeNode definition

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

Approach 1: BFS with column tracking

BFS ensures nodes at shallower levels appear before deeper ones within the same column. This is the standard approach for most vertical order problems.

from collections import deque, defaultdict

def verticalOrder(root):
    """
    Vertical order traversal using BFS.
    Time: O(n log n) due to sorting columns
    Space: O(n)
    """
    if not root:
        return []

    column_map = defaultdict(list)
    queue = deque([(root, 0)])  # (node, column)
    min_col = 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))

    # Collect columns from leftmost to rightmost
    return [column_map[col] for col in range(min_col, max_col + 1)]

Why BFS and not DFS?

BFS processes nodes level by level. Within the same column, we want nodes from higher levels to appear before nodes from lower levels. BFS guarantees this naturally. DFS would require sorting by row number afterward.

Step-by-step walkthrough

Tree:
         1 (col=0)
        / \
       2   3 (col=-1, col=1)
      / \   \
     4   5   7 (col=-2, col=0, col=2)

Step	Dequeue	Column	column_map update
1	(1, 0)	0	{0: [1]}
2	(2, -1)	-1	{0: [1], -1: [2]}
3	(3, 1)	1	{0: [1], -1: [2], 1: [3]}
4	(4, -2)	-2	{-2: [4], -1: [2], 0: [1], 1: [3]}
5	(5, 0)	0	{-2: [4], -1: [2], 0: [1, 5], 1: [3]}
6	(7, 2)	2	{-2: [4], -1: [2], 0: [1, 5], 1: [3], 2: [7]}

Result: [[4], [2], [1, 5], [3], [7]]

Approach 2: LeetCode 987 — strict vertical order

LeetCode 987 has a stricter definition: if two nodes are at the same row and column, sort them by value. This requires tracking the row as well.

from collections import defaultdict

def verticalTraversal(root):
    """
    LeetCode 987: Vertical Order Traversal.
    Nodes at same (row, col) are sorted by value.
    Time: O(n log n)  Space: O(n)
    """
    if not root:
        return []

    # Store (row, val) pairs grouped by column
    column_map = defaultdict(list)
    min_col = max_col = 0

    queue = deque([(root, 0, 0)])  # (node, row, col)

    while queue:
        node, row, col = queue.popleft()
        column_map[col].append((row, node.val))

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

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

    result = []
    for col in range(min_col, max_col + 1):
        # Sort by row first, then by value (for same row)
        column_map[col].sort()
        result.append([val for _, val in column_map[col]])

    return result

Difference from basic vertical order

In the basic version, nodes at the same column appear in BFS order. In the strict version, nodes at the same row and column are sorted by value. This matters when two nodes occupy the exact same position:

      1
     / \
    2   3
     \ /
      4    ← both children point to col 0, row 2

Basic: order depends on BFS (left child processed first) Strict: sort by value among nodes at same (row, col)

Top view of a binary tree

The top view shows the first node seen in each column when looking from above. For each column, we only want the node at the smallest row (shallowest depth).

from collections import deque

def topView(root):
    """
    Top view: first node at each column (smallest row).
    Time: O(n)  Space: O(n)
    """
    if not root:
        return []

    column_map = {}
    queue = deque([(root, 0)])
    min_col = max_col = 0

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

        # Only record the first node seen at this column
        if col not in column_map:
            column_map[col] = 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)]

Since BFS processes level by level, the first node encountered in each column is the topmost. We simply check if col not in column_map and only store the first occurrence.

Bottom view of a binary tree

The bottom view shows the last node seen in each column. We overwrite the column entry for each node, so the last one (deepest, rightmost in BFS order) wins.

def bottomView(root):
    """
    Bottom view: last node at each column (largest row).
    Time: O(n)  Space: O(n)
    """
    if not root:
        return []

    column_map = {}
    queue = deque([(root, 0)])
    min_col = max_col = 0

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

        # Always overwrite — last node at this column wins
        column_map[col] = 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)]

Top view vs bottom view — the only difference

View	Strategy	Code difference
Top view	Keep first node per column	if col not in column_map
Bottom view	Keep last node per column	Always overwrite column_map[col]

Vertical sum

Another common variant: instead of listing nodes, sum all values in each column.

def verticalSum(root):
    """
    Sum of values at each vertical column.
    Time: O(n)  Space: O(n)
    """
    if not root:
        return []

    column_sums = defaultdict(int)
    min_col = max_col = 0

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

    while queue:
        node, col = queue.popleft()
        column_sums[col] += 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_sums[col] for col in range(min_col, max_col + 1)]

DFS alternative

If you prefer DFS, you can track (row, col) and sort afterward:

def verticalOrderDFS(root):
    """
    DFS approach — requires sorting by (col, row, val).
    Time: O(n log n)  Space: O(n)
    """
    if not root:
        return []

    nodes = []  # (col, row, val)

    def dfs(node, row, col):
        if not node:
            return
        nodes.append((col, row, node.val))
        dfs(node.left, row + 1, col - 1)
        dfs(node.right, row + 1, col + 1)

    dfs(root, 0, 0)
    nodes.sort()  # Sort by col, then row, then val

    result = []
    prev_col = None
    for col, row, val in nodes:
        if col != prev_col:
            result.append([])
            prev_col = col
        result[-1].append(val)

    return result

The DFS approach is simpler to write but requires explicit sorting, making it O(n log n). BFS is O(n) when we track min/max columns instead of sorting.

Complexity analysis

Problem	Time	Space	Key insight
Vertical order (BFS)	O(n)	O(n)	Track min/max col, iterate range
Vertical order (DFS)	O(n log n)	O(n)	Must sort by (col, row)
Strict vertical (LC 987)	O(n log n)	O(n)	Sort within columns by (row, val)
Top view	O(n)	O(n)	First node per column
Bottom view	O(n)	O(n)	Last node per column
Vertical sum	O(n)	O(n)	Sum instead of list

Edge cases

def test_edge_cases():
    # Empty tree
    assert verticalOrder(None) == []

    # Single node
    root = TreeNode(1)
    assert verticalOrder(root) == [[1]]
    assert topView(root) == [1]
    assert bottomView(root) == [1]

    # Left-skewed: each node goes to a new column
    root = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert verticalOrder(root) == [[3], [2], [1]]

    # Right-skewed
    root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
    assert verticalOrder(root) == [[1], [2], [3]]

Common mistakes

1. Using DFS without sorting: DFS does not guarantee level order within a column. You must sort by row.

2. Sorting columns by key instead of range: Using sorted(column_map.keys()) works but is O(c log c). Tracking min/max and using range() is O(c).

3. Confusing top/bottom view with left/right view: Views from left/right show the first/last node at each level. Top/bottom views show the first/last node at each column.

4. Not handling overlapping nodes: When two nodes share the same (row, col), the problem definition determines the tiebreaker. Read the problem statement carefully.

Practice problems

Problem	Difficulty	Link
Vertical Order Traversal	Hard	LeetCode 987
Binary Tree Vertical Order Traversal	Medium	LeetCode 314
Binary Tree Right Side View	Medium	LeetCode 199
Top View of Binary Tree	Medium	GeeksforGeeks
Bottom View of Binary Tree	Medium	GeeksforGeeks

Key takeaways

1. Vertical order assigns column indices: left child = col-1, right child = col+1
2. BFS naturally preserves level order within columns — preferred for vertical traversal
3. Top view = first node per column; bottom view = last node per column
4. LeetCode 987 adds row-based tiebreaking — sort within each column
5. Track min/max columns to avoid sorting the column keys