Skip to main content

987 - Vertical Order Traversal of a Binary Tree

Difficulty: Hard | Pattern: BFS/DFS + Sorting | Company tags: Facebook, Amazon, Google

Problem Statement​

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root is at (0, 0).

The vertical order traversal is a list of top-to-bottom orderings for each column index from left to right. If two nodes are in the same row and column, sort by value.

Example:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Solution: DFS + Grouping — O(n log n)​

from collections import defaultdict

def verticalTraversal(root) -> list[list[int]]:
    nodes = []
    
    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)
    
    # Sort by (col, row, val)
    nodes.sort()
    
    result = []
    groups = defaultdict(list)
    for col, row, val in nodes:
        groups[col].append(val)
    
    for col in sorted(groups.keys()):
        result.append(groups[col])
    
    return result

Algorithm Flow​

Dry Run​

Tree: 3(root), left=9, right=20(left=15,right=7)

Nodes collected (col, row, val):

  • (0, 0, 3)
  • (-1, 1, 9)
  • (1, 1, 20)
  • (0, 2, 15)
  • (2, 2, 7)

Sorted: (-1,1,9), (0,0,3), (0,2,15), (1,1,20), (2,2,7)

Groups: col-1→[9], col0→[3,15], col1→[20], col2→[7]

Result: [[9],[3,15],[20],[7]] ✓

Key Tie-Breaking Rule​

When col and row are the same, sort by value. The sort() on (col, row, val) tuples handles this automatically since Python sorts tuples lexicographically.

Complexity​

  • Time: O(n log n) — sorting dominates
  • Space: O(n)

Key Terms​

TermDefinition
Vertical columnSet of nodes sharing the same col value computed via (row+1, col-1)/(row+1, col+1) offsets.
Tuple sortSorting (col, row, val) tuples lexicographically to resolve column order, then row order, then value tie-breaks in one pass.
Tie-breakingWhen two nodes share (row, col), the smaller value is listed first.
DFS with coordinatesRecursion that threads (row, col) state through each call instead of just visiting nodes.
Grouping by keyPost-processing step (e.g. defaultdict(list)) that buckets sorted items by their column key.

FAQ​

  1. Can this be solved without sorting the full node list? Yes — use a BFS level-order traversal per column and merge columns with a min-heap keyed by (col, row, val), but plain sorting is simpler and still O(n log n).
  2. What if the tree is empty? dfs(None, ...) returns immediately, nodes stays empty, and the function returns [].
  3. How would this differ from problem 314 (Binary Tree Vertical Order Traversal)? 314 only requires top-to-bottom BFS order within a column (no value tie-break), so a queue-based BFS with column buckets suffices without sorting by value.
  4. Why use DFS instead of BFS here? Either works since we collect all (col, row, val) triples before sorting; DFS is simpler to code recursively, BFS naturally gives row order per level.
  5. What breaks if row is omitted from the sort key? Nodes at different depths in the same column could be ordered by value alone, corrupting the required top-to-bottom sequence.

Quick Revision​

  • Track (row, col) for every node starting at root (0, 0).
  • Left child: (row+1, col-1); right child: (row+1, col+1).
  • Collect (col, row, val) triples via DFS or BFS.
  • Sort triples lexicographically — this handles column, then row, then value tie-break in one shot.
  • Group sorted triples by col into the final list of lists.
  • Return columns ordered from leftmost (smallest col) to rightmost.
  • Time is dominated by sorting: O(n log n); space is O(n) for the triples list.
  • Contrast with problem 314, which skips the value tie-break and can use BFS + column dict alone.