Binary Tree Vertical Order Traversal
Problem
Given the root of a binary tree, return the vertical order traversal of its nodes' values. Nodes with the same horizontal distance are grouped together, and the order is from leftmost column to rightmost column, traversing nodes top to bottom within each column.
- The number of nodes in the tree is in the range [0, 1000]
- −1000 ≤ Node.val ≤ 1000
Example
root = [3,9,20,null,null,15,7][[9],[3,15],[20],[7]]Begin with queue = [(3, 0)] and columns = {}. We start by placing the root in the queue with column 0 because the root is the reference point for all other column positions. The columns map will group node values by their vertical column. Pop (3, 0), record it in column 0, and enqueue (9, -1) and (20, 1). We add 3 to column 0 because that is the root's vertical position. Then we enqueue its children with updated column indices: moving left means column -1, and moving right means column +1. This is how we keep track of each node's horizontal position. Pop (9, -1) and record it in column -1. Node 9 is one column to the left of the root, so it belongs in column -1. It has no children, so there is nothing else to enqueue from this node. Pop (20, 1), record it in column 1, and enqueue (15, 0) and (7, 2). Node 20 is one column to the right of the root, so it goes into column 1. Its left child 15 moves back to column 0, and its right child 7 moves further right to column 2. This preserves each child's vertical position relative to its parent. Pop (15, 0) and add it to column 0, then pop (7, 2) and add it to column 2. Node 15 shares the same vertical column as the root, so it is appended to column 0 after 3. Node 7 belongs in column 2 because it is two steps to the right of the root. After BFS, columns = {-1: [9], 0: [3, 15], 1: [20], 2: [7]}. At this point, every node has been visited exactly once, and each value has been placed into the correct vertical column. Since min_col = -1 and max_col = 2, iterate from -1 through 2, append each columns[c] into output, and get [[9], [3,15], [20], [7]]. We iterate from the smallest column to the largest so the final result is ordered from the leftmost vertical line to the rightmost vertical line, which is exactly what the problem asks for. Return output.
Approach
Straightforward Solution
A naive approach might perform a DFS and record nodes by column, but this risks mixing node order within columns because DFS explores depth-first, not level-by-level. This can lead to incorrect vertical ordering when nodes share the same column but different depths.
Core Observation
Vertical order traversal requires grouping nodes by their horizontal distance (column) from the root, and ordering nodes top to bottom within each column. This naturally maps to a breadth-first search (BFS) traversal where each node is associated with a column index, allowing level-order processing that preserves top-to-bottom order.
Path to Optimal
The key insight is to use BFS to traverse the tree level by level, associating each node with its column index. By processing nodes in BFS order, nodes at the same depth and column are visited in left-to-right order, preserving the required top-to-bottom order within columns. Using a hash map keyed by column indices collects nodes per column, and tracking min and max column indices allows outputting columns in order.
Optimal Approach
Perform a BFS starting from the root at column 0. Use a queue to store pairs of (node, column). For each dequeued node, append its value to the list for its column in a dictionary. Update min and max column indices to track the range of columns seen. Enqueue left and right children with column indices decremented and incremented respectively. After BFS completes, iterate from min_col to max_col and collect the lists of node values to form the final vertical order traversal.
Time
O(n)
Each node is enqueued and dequeued exactly once during BFS, resulting in linear time proportional to the number of nodes.
Space
O(n)
The auxiliary space includes the queue and the dictionary storing nodes per column. In the worst case, all nodes could be stored in these structures, leading to O(n) space.
Pattern Spotlight
BFS (Layered Graph Traversal with State Tracking)
When node order within levels matters and nodes must be grouped by a derived key (like column), BFS combined with a queue that tracks both node and state (column) ensures correct top-to-bottom ordering and efficient grouping.
Solution
| 1 | class Solution: |
| 2 | def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]: |
| 3 | if not root: |
| 4 | return [] |
| 5 | |
| 6 | columns = defaultdict(list) |
| 7 | queue = deque([(root, 0)]) |
| 8 | |
| 9 | min_col = 0 |
| 10 | max_col = 0 |
| 11 | |
| 12 | while queue: |
| 13 | node, col = queue.popleft() |
| 14 | |
| 15 | columns[col].append(node.val) |
| 16 | |
| 17 | min_col = min(min_col, col) |
| 18 | max_col = max(max_col, col) |
| 19 | |
| 20 | if node.left: |
| 21 | queue.append((node.left, col - 1)) |
| 22 | |
| 23 | if node.right: |
| 24 | queue.append((node.right, col + 1)) |
| 25 | |
| 26 | output = [] |
| 27 | |
| 28 | for c in range(min_col, max_col + 1): |
| 29 | output.append(columns[c]) |
| 30 | |
| 31 | return output |
Step-by-Step Solution
Return Empty List for Null Tree Input
| 3 | if not root: |
| 4 | return [] |
Objective
To handle the edge case where the input tree is empty by returning an empty list immediately.
Key Insight
Checking for a null root upfront prevents unnecessary processing and avoids errors. This early exit is a standard defensive programming practice that handles trivial input gracefully.
Interview Quick-Check
State & Boundaries
Return [] immediately if root is None, as there are no nodes to traverse.
Initialize BFS Queue and Column Storage
| 6 | columns = defaultdict(list) |
| 7 | queue = deque([(root, 0)]) |
| 9 | min_col = 0 |
| 10 | max_col = 0 |
Objective
To set up the data structures needed for BFS traversal and column grouping.
Key Insight
A queue initialized with the root node and its column index 0 enables level-order traversal while tracking horizontal distance. A dictionary keyed by column indices collects node values per column. Tracking min_col and max_col bounds the range of columns encountered, allowing ordered output later.
Interview Quick-Check
Core Logic
Using a queue of (node, column) pairs enables BFS traversal that maintains column information for each node.
Core Logic
The columns dictionary groups node values by their column index, facilitating vertical order grouping.
State & Boundaries
min_col and max_col track the smallest and largest column indices seen, defining the output range.
Traverse Tree with BFS and Group Nodes by Column
| 12 | while queue: |
| 13 | node, col = queue.popleft() |
| 15 | columns[col].append(node.val) |
| 17 | min_col = min(min_col, col) |
| 18 | max_col = max(max_col, col) |
| 20 | if node.left: |
| 21 | queue.append((node.left, col - 1)) |
| 23 | if node.right: |
| 24 | queue.append((node.right, col + 1)) |
Objective
To perform BFS traversal, appending node values to their respective column lists and updating column boundaries.
Key Insight
BFS ensures nodes are processed in top-to-bottom order. For each node, appending its value to the column list preserves the vertical order. Updating min_col and max_col dynamically tracks the full column range. Enqueuing left and right children with adjusted column indices propagates the horizontal distance correctly.
Interview Quick-Check
Core Logic
BFS processes nodes level by level, ensuring vertical order within columns is maintained.
Core Logic
Appending node values to columns[col] groups nodes by their horizontal distance.
State & Boundaries
Updating min_col and max_col ensures the final output covers all columns from leftmost to rightmost.
Common Pitfalls & Bugs
Forgetting to enqueue children with correct column indices (col - 1 for left, col + 1 for right) breaks the horizontal distance tracking.
Collect and Return Vertical Order from Column Groups
| 26 | output = [] |
| 28 | for c in range(min_col, max_col + 1): |
| 29 | output.append(columns[c]) |
| 31 | return output |
Objective
To assemble the final output list by iterating over the range of columns and collecting grouped node values.
Key Insight
Iterating from min_col to max_col in order ensures the output lists are arranged from leftmost to rightmost columns. Appending the lists from the columns dictionary produces the vertical order traversal as required.
Interview Quick-Check
Core Logic
Iterating over the column range in order produces the final vertical order traversal.
State & Boundaries
Using min_col and max_col ensures no columns are skipped or duplicated.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
columns = defaultdict(list)Initialize a dictionary to map column indices to lists of node values.
This data structure is essential for grouping nodes by their horizontal distance, enabling efficient vertical order collection.
queue = deque([(root, 0)])Initialize a queue with the root node and its column index 0.
The queue supports BFS traversal, and storing the column index with each node allows tracking horizontal distance during traversal.
columns[col].append(node.val)Append the current node's value to its column's list.
This groups nodes by their horizontal distance, preserving the order in which nodes are visited (top to bottom).
if not root:Check if the root is None (empty tree).
This early check prevents unnecessary computation and handles the edge case of an empty tree by returning an empty list immediately.
node, col = queue.popleft()Dequeue the next node and its column index.
Dequeuing in FIFO order maintains BFS traversal order, ensuring nodes are processed by depth and left-to-right within each level.
if node.left:If the current node has a left child, enqueue it with column index decremented by 1.
Assigning the left child to column col - 1 correctly tracks horizontal distance, enabling proper grouping in vertical order.
if node.right:If the current node has a right child, enqueue it with column index incremented by 1.
Assigning the right child to column col + 1 correctly tracks horizontal distance, enabling proper grouping in vertical order.
output.append(columns[c])Append the list of node values for the current column to the output.
Collecting the column lists in order produces the final vertical order traversal output.
return []Return an empty list for an empty tree.
Returning [] here correctly signals that no vertical order traversal exists for an empty input.
while queue:Continue BFS while there are nodes in the queue.
The loop ensures all nodes are processed in level order, which is critical for preserving vertical order top-to-bottom within columns.
min_col = min(min_col, col)Update min_col if the current column is smaller.
Maintaining the smallest column index seen ensures the output includes all columns from left to right without omission.
max_col = max(max_col, col)Update max_col if the current column is larger.
Maintaining the largest column index seen ensures the output includes all columns from left to right without omission.
queue.append((node.left, col - 1))Add the left child and its column to the queue for BFS.
Enqueuing the left child ensures it will be processed in BFS order, preserving top-to-bottom traversal within columns.
queue.append((node.right, col + 1))Add the right child and its column to the queue for BFS.
Enqueuing the right child ensures it will be processed in BFS order, preserving top-to-bottom traversal within columns.
for c in range(min_col, max_col + 1):Iterate over the range of columns from min_col to max_col inclusive.
Iterating in order ensures the output respects the left-to-right column ordering required by vertical traversal.
min_col = 0Initialize min_col to track the leftmost column index encountered.
Tracking min_col allows the algorithm to know the left boundary of the vertical order output range.
max_col = 0Initialize max_col to track the rightmost column index encountered.
Tracking max_col allows the algorithm to know the right boundary of the vertical order output range.
return outputReturn the assembled vertical order traversal list.
Returning the output completes the function, providing the caller with the correctly ordered vertical traversal.
output = []Initialize the output list to collect vertical order traversal results.
This list will accumulate the grouped node values from leftmost to rightmost columns for the final return.
Test Your Understanding
Why is BFS preferred over DFS for vertical order traversal when nodes must be ordered top to bottom within columns?
Because BFS processes nodes level by level, it naturally preserves the top-to-bottom order within each column. DFS explores depth-first and can visit deeper nodes before shallower ones in the same column, which breaks the required vertical ordering.
Related Problems
BFS pattern
Don't just read it. Drill it.
Reconstruct Binary Tree Vertical Order Traversal from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Binary Tree Vertical Order Traversal drill