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

⌘K

Tutor

Get Premium

Leetcode 987. Vertical Order Traversal of a Binary Tree

Assign each node coordinates (row, col) with root at (0,0) and children at (r+1,c±1), then produce a list of columns from leftmost to rightmost where nodes in each column are ordered by increasing row and, for nodes with the same row and column, by increasing node value.

Asked at:

Meta

DESCRIPTION

Input:

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

Output:

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

Explanation: Root 3 is at (0,0). Left child 9 is at (1,-1). Right child 20 is at (1,1). Node 15 is at (2,0) and node 7 is at (2,2). Grouping by column: col -1 has [9], col 0 has [3,15], col 1 has [20], col 2 has [7]

Constraints:

The number of nodes in the tree is in the range [1, 1000]
0 <= Node.val <= 1000
Nodes in the same row and column should be sorted by increasing value

Understanding the Problem

Let's understand what we're being asked to do. We have a binary tree, and we need to assign coordinates to each node. The root starts at position (0, 0), and for any node at (row, col), its left child goes to (row+1, col-1) and its right child goes to (row+1, col+1).

For example, if the root (value 3) is at (0,0), its left child (value 9) would be at (1,-1) and its right child (value 20) would be at (1,1). If node 20 has children 15 and 7, they'd be at (2,0) and (2,2) respectively.

Once we have coordinates, we need to group nodes by their column (the col value). Within each column, nodes should be ordered by increasing row, and if two nodes share the same row and column, they should be ordered by increasing node value.

Important constraint: The output should list columns from leftmost to rightmost (smallest col to largest col).

Edge cases to consider: What if the tree is just a single node? What if the tree is heavily skewed to one side? What if multiple nodes end up at the same (row, col) position?

Building Intuition

As we traverse the tree, each node naturally gets a unique (row, col) coordinate based on its position. The column value acts as a natural grouping key.

Nodes in the same column need to be sorted by row first, then by value if they share the same row. This means we need to collect all nodes with their coordinates before we can organize them into the final output.

By tracking coordinates during traversal, we transform a tree structure problem into a sorting and grouping problem. Once we have all coordinates, we can group by column, sort within each group, and output columns in left-to-right order.

This separation of concerns (traverse to collect data, then organize data) makes the solution clearer and easier to implement correctly.

Imagine taking a photo of the tree from above and projecting all nodes onto a horizontal line based on their column values.

Nodes at col=-2 form the leftmost group, nodes at col=-1 form the next group, and so on. Within each vertical column, nodes are stacked by their row (depth in tree), and if two nodes somehow end up at the same position, we list the smaller value first.

The key insight is that we need to visit every node to know its coordinates before we can organize the final output.

Common Mistakes

Forgetting to track the row coordinate - only tracking column is insufficient because nodes in the same column need to be ordered by row

Not handling the tie-breaking case when multiple nodes have the same (row, col) - they must be sorted by node value

Trying to output columns during traversal instead of collecting all data first - this fails because we don't know the leftmost column until we've seen all nodes

Using the wrong traversal order - while both BFS and DFS work, the implementation must correctly track coordinates as it moves left (col-1) and right (col+1)

Not sorting columns by their column number before outputting - the final result must go from leftmost to rightmost column

Optimal Solution

Use BFS or DFS to traverse the tree while tracking each node's (row, col) coordinates. Store each node along with its coordinates in a data structure. After traversal, group nodes by column, sort each column's nodes by row (and by value for ties), then output columns from leftmost to rightmost. This approach ensures we visit every node exactly once and then organize the results efficiently.

Visualization

from collections import defaultdict, deque
def vertical_order_traversal(root):
    """
    Perform vertical order traversal with coordinate tracking.
    Returns columns from left to right, nodes sorted by row then value.
    """
    if not root:
        return []
    
    # Dictionary to store nodes by column: col -> [(row, val)]
    columns = defaultdict(list)
    
    # BFS queue: (node, row, col)
    queue = deque([(root, 0, 0)])
    
    # Track min and max columns for ordering
    min_col = 0
    max_col = 0
    
    # BFS traversal to assign coordinates
    while queue:
        node, row, col = queue.popleft()
        
        # Store node with its coordinates
        columns[col].append((row, node.val))
        
        # Update column bounds
        min_col = min(min_col, col)
        max_col = max(max_col, col)
        
        # Add children with updated coordinates
        if node.left:
            queue.append((node.left, row + 1, col - 1))
        if node.right:
            queue.append((node.right, row + 1, col + 1))
    
    # Build result: sort each column and collect from left to right
    result = []
    for col in range(min_col, max_col + 1):
        # Sort by row first, then by value for ties
        sorted_nodes = sorted(columns[col], key=lambda x: (x[0], x[1]))
        # Extract just the values
        result.append([val for row, val in sorted_nodes])
    
    return result

Start vertical order traversal

0 / 48

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log n) We visit each of the n nodes once during traversal (O(n)), then sort nodes within each column. In the worst case, all nodes could be in one column, requiring O(n log n) sorting. Overall time is O(n log n).

Space Complexity: O(n) We store all n nodes with their coordinates in a hash map or list, requiring O(n) space. The recursion stack (if using DFS) or queue (if using BFS) also uses O(n) space in the worst case.

What We've Learned

HashMap + TreeMap coordinate mapping: When problems require grouping by one dimension (column) and sorting by multiple criteria within groups, use a HashMap<Integer, TreeMap<Integer, PriorityQueue>> structure - the outer map groups by column, TreeMap auto-sorts rows, and PriorityQueue handles same-position value ordering.
DFS with coordinate tracking: Tree traversal problems requiring positional awareness benefit from passing (row, col) parameters through recursive calls - increment row by 1 for depth, adjust col by ±1 for left/right children to build a coordinate system naturally during traversal.
Multi-level sorting strategy: When sorting requires multiple criteria (row, then value), don't try complex comparators on raw data - instead use nested sorted structures (TreeMap for rows containing PriorityQueues for values) to handle each sorting dimension independently and automatically.
Column range discovery pitfall: Don't assume columns range from 0 to n-1 - a skewed tree can have columns like -3, -2, 0, 1. Always discover the actual column range during traversal or use a map that handles arbitrary integer keys rather than array indexing.
BFS vs DFS equivalence with coordinates: Both BFS and DFS work here because we're storing (row, col, value) tuples and sorting afterward - the traversal order doesn't matter when you're collecting all data first. Choose DFS for simpler code or BFS if you need true level-order guarantees.
Vertical slicing pattern: This coordinate-based grouping technique extends to any problem requiring projection onto axes - think calendar scheduling (time axis), building skylines (x-coordinate grouping), or organizing 2D data into vertical/horizontal bands for processing.

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

Mid-level

Mid November, 2025

Meta

Senior

Early November, 2025

Meta

Mid-level

Get Premium to View All 10+ 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 987. Vertical Order Traversal of a Binary Tree

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