Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 314. Binary Tree Vertical Order Traversal

Group tree nodes by their horizontal (column) index and return a list of columns from leftmost to rightmost, preserving top-to-bottom order and left-to-right ordering for nodes that share the same position—commonly solved by BFS/level-order traversal with column indices and a map.

Asked at:

Meta

Uber

DESCRIPTION

Input:

nodes = [3,9,20,null,null,15,7]

Output:

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

Explanation: Column -1: [9], Column 0: [3,15], Column 1: [20], Column 2: [7]. Nodes are grouped by column and ordered top-to-bottom, left-to-right

Constraints:

The number of nodes in the tree is in the range [1, 1000]
-1000 <= Node.val <= 1000
Nodes at the same position must preserve their left-to-right order in the tree
Return columns from leftmost to rightmost

Understanding the Problem

Let's understand what we're being asked to do. We have a binary tree where each node has a position, and we need to group nodes by their horizontal distance from the root.

Imagine the root at column 0. Its left child is at column -1, right child at column 1. The left child's left child is at column -2, and so on.

For example, given a tree:

Node 3 is at column 0, node 9 is at column -1, node 20 is at column 1, node 15 is at column 0, node 7 is at column 2.

Grouping by column: [-1: [9], 0: [3,15], 1: [20], 2: [7]]. Return as [[9], [3,15], [20], [7]] (leftmost to rightmost).

Important constraint: When multiple nodes share the same position (same row AND column), preserve their left-to-right order as they appear in the tree.

Edge cases to consider: What if the tree is just one node? What if all nodes are in a single column (like a linked list)? What if nodes at the same position need ordering?

Building Intuition

Each node can be assigned a column index based on its position relative to the root. If we go left, we subtract 1 from the column; if we go right, we add 1.

This means every node in the tree has a unique (row, column) coordinate. Nodes with the same column index belong to the same vertical line.

By tracking column indices as we traverse the tree, we can group nodes by their column using a map or dictionary.

The challenge is ensuring we visit nodes in the correct order: top-to-bottom (by level) and left-to-right (within each level). This ordering ensures nodes at the same position are processed in the right sequence.

Think of the tree as a 2D grid where the root is at position (0, 0). Each node's children are offset by ±1 in the column direction.

If we explore the tree level by level (like reading a book: left-to-right, top-to-bottom), we naturally visit nodes in the correct order. As we visit each node, we record its value in a map under its column index.

This level-order traversal pattern ensures that when multiple nodes share the same column, they're added in top-to-bottom, left-to-right order automatically.

Common Mistakes

Using DFS instead of BFS - DFS doesn't guarantee top-to-bottom ordering within the same column, leading to incorrect ordering when nodes share positions

Forgetting to track column indices - without column tracking, there's no way to group nodes by their horizontal position

Not sorting the final columns by index - hash maps don't maintain insertion order, so columns must be explicitly sorted from leftmost to rightmost

Incorrect column index updates - forgetting that left child is column - 1 and right child is column + 1 leads to wrong groupings

Not handling null nodes properly - adding null nodes to the queue will cause errors; only non-null children should be enqueued with their column indices

Optimal Solution

Use BFS (level-order traversal) with a queue to traverse the tree while tracking each node's column index. Start with the root at column 0. For each node, add its left child at column - 1 and right child at column + 1 to the queue. Use a hash map to group nodes by their column index. BFS naturally ensures top-to-bottom and left-to-right ordering. Finally, sort the columns by their index and return the grouped values.

Visualization

from collections import deque, defaultdict
def vertical_order_traversal(root):
    """
    Group tree nodes by column index using BFS with column tracking.
    Returns list of columns from leftmost to rightmost.
    """
    if not root:
        return []
    
    # Map to store nodes by column index
    column_map = defaultdict(list)
    
    # Queue stores (node, column_index) tuples
    queue = deque([(root, 0)])
    
    # BFS traversal with column tracking
    while queue:
        node, col = queue.popleft()
        
        # Add node value to its column
        column_map[col].append(node.val)
        
        # Add left child at column - 1
        if node.left:
            queue.append((node.left, col - 1))
        
        # Add right child at column + 1
        if node.right:
            queue.append((node.right, col + 1))
    
    # Sort columns by index and extract values
    sorted_columns = sorted(column_map.keys())
    result = [column_map[col] for col in sorted_columns]
    
    return result

Start vertical order traversal

0 / 36

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log n) We visit each of the n nodes exactly once during BFS traversal (O(n)), then sort the columns by their indices. In the worst case (skewed tree), we might have n columns to sort, giving O(n log n) overall

Space Complexity: O(n) We use a queue for BFS that can hold up to O(n) nodes in the worst case (complete tree's last level), and a hash map storing all n nodes grouped by column, resulting in O(n) space

What We've Learned

BFS with column tracking: Use BFS (level-order traversal) instead of DFS for vertical order problems because BFS naturally preserves top-to-bottom ordering - nodes at the same column are discovered in the correct vertical sequence, whereas DFS would require additional sorting by depth.
HashMap with column indices: Maintain a HashMap<Integer, List<Integer>> where keys are column indices (left child = parent_col - 1, right child = parent_col + 1) - this allows O(1) grouping of nodes by column while tracking the min/max column bounds for final ordering.
Queue pairing technique: Store pairs of (node, column_index) in your BFS queue rather than just nodes - this propagates positional information through the traversal without needing a separate data structure or parent lookups.
Column range tracking: Track min and max column indices during traversal to avoid sorting HashMap keys at the end - iterate from min to max column for O(k) final assembly where k is the column range, much faster than O(k log k) sorting.
Coordinate system problems: This 2D coordinate mapping pattern (assigning x/y or column/row indices to tree nodes) applies to any problem requiring spatial grouping: boundary traversal, diagonal traversal, or printing trees in specific layouts.
Left-to-right guarantee: When nodes share the same position (same column and depth), BFS with left-child-before-right-child queue insertion automatically preserves left-to-right order without explicit tie-breaking logic - this is a key advantage over DFS approaches.

Test Your Understanding

Why is tree the right data structure for this problem?

tree provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late November, 2025

Meta

Staff

Mid November, 2025

Meta

Staff

Early November, 2025

Meta

Mid-level

Get Premium to View All 50+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 314. Binary Tree Vertical Order Traversal

DESCRIPTION

Understanding the Problem

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact