Leetcode 314. Binary Tree Vertical Order Traversal

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:

    3
   / \
  9  20
    /  \
   15   7

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?

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.

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.

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

• 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.