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
PreviewThe 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewPerform a BFS starting from the root at column 0. Use a queue to store pairs of (node, column)…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
To set up the data structures needed for BFS traversal and column grouping.
Traverse Tree with BFS and Group Nodes by Column
To perform BFS traversal, appending node values to their respective column lists and updating column boundaries.
Collect and Return Vertical Order from Column Groups
To assemble the final output list by iterating over the range of columns and collecting grouped node values.
3 more steps with full analysis available on Pro.
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).
Full line-by-line criticality + rationale for all 19 lines available on Pro.
Test Your Understanding
Why is BFS preferred over DFS for vertical order traversal when nodes must be ordered top to bottom within columns?
See the answer with Pro.
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