Leetcode 987. Vertical Order Traversal of a Binary Tree

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?

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.

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.

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

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