LeetCode Solutions Blog

Vertical Order Traversal of a Binary Tree

Number: 1029

Difficulty: Hard

Paid? No

Problem Description

Given the root of a binary tree, return its vertical order traversal. Each node is assigned a coordinate (row, col) with the root at (0, 0). The left child of a node at (row, col) is at (row + 1, col - 1) and the right child at (row + 1, col + 1). For nodes in the same column, they should be sorted first by row and then by their value if they share the same row. The output is a list of lists containing the vertical order, spanning from the leftmost to the rightmost column.

Key Insights

Each node is annotated with a (row, col) coordinate during traversal.
Use BFS (or DFS) to traverse the tree and record each node’s position.
For nodes in the same column and row, sort by their values.
Utilize a hash table (dictionary or map) to associate column indices with lists of (row, value) pairs.
Extract and sort by column indices for the final output.

Space and Time Complexity

Time Complexity: O(N log N) — O(N) to traverse and O(N log N) overall sorting cost in the worst case. Space Complexity: O(N) — to store node coordinates in the auxiliary data structures.

Solution

We traverse the tree using BFS while tracking each node’s (row, col) coordinates. During the traversal, we store each node’s information in a hash table mapping column indices to a list of (row, value) pairs. After the traversal, for each column we sort the list of nodes by row and, in case of ties, by node value. Finally, we output the values column by column from the leftmost to the rightmost column.

Code Solutions

from collections import deque, defaultdict

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def verticalTraversal(root):
    # Dictionary mapping column index to list of (row, value) tuples.
    col_map = defaultdict(list)
    # Queue for BFS: each element is a tuple (node, row, col)
    queue = deque([(root, 0, 0)])
    
    while queue:
        node, row, col = queue.popleft()
        if node:
            col_map[col].append((row, node.val))
            # Enqueue left and right children with updated row and col values.
            queue.append((node.left, row + 1, col - 1))
            queue.append((node.right, row + 1, col + 1))
    
    result = []
    # Process each column sorted by the column index.
    for col in sorted(col_map.keys()):
        # Sort nodes by row and then by value.
        col_entries = sorted(col_map[col], key=lambda x: (x[0], x[1]))
        result.append([val for row, val in col_entries])
    return result

# Example usage:
# Constructing the tree [3,9,20,null,null,15,7]
node15 = TreeNode(15)
node7 = TreeNode(7)
node20 = TreeNode(20, node15, node7)
node9 = TreeNode(9)
root = TreeNode(3, node9, node20)
print(verticalTraversal(root))