Binary Tree Vertical Order Traversal
Understanding the Problem
We're given a binary tree and need to return node values grouped by their vertical column. Place the tree on a grid with the root at column 0. Every left edge decreases the column by 1, and every right edge increases it by 1. Nodes that land in the same column form one group.
Within a column, nodes appear from top to bottom. If two nodes share both the same column and the same row, the one further to the left in the tree comes first. This tie-breaking rule is what makes BFS a good fit: BFS processes nodes level by level, left to right, which is the required order.
The main work is grouping nodes by column and returning the columns in left-to-right order.
Key Constraints:
0 <= number of nodes <= 100: The tree can be empty (root = null), in which case the answer is an empty list. The small size means performance does not decide between the approaches below, though the algorithmic difference matters for larger inputs.-100 <= Node.val <= 100: Values can be negative. Column indices can also be negative (any node to the left of the root), so the grouping structure must accept negative keys.
Approach 1: BFS + HashMap + Sorting
Intuition
Traverse the tree, assign a column index to every node, and group values by column. BFS processes nodes level by level, which gives the correct top-to-bottom ordering within each column, and within a level it visits nodes left to right, which satisfies the tie-breaking rule.
For each node, we store its value in a hash map keyed by column index. The root starts at column 0. When we visit a node at column c, its left child goes to column c - 1 and its right child to column c + 1. After the traversal, we sort the hash map keys to arrange columns from leftmost to rightmost.
Algorithm
- If the root is null, return an empty list.
- Create a hash map to store column index to list of node values.
- Create a BFS queue. Enqueue the root with column index 0.
- While the queue is not empty:
- Dequeue a node and its column index.
- Add the node's value to the hash map entry for that column.
- If the node has a left child, enqueue it with column index
column - 1. - If the node has a right child, enqueue it with column index
column + 1. - Sort the hash map keys.
- For each key in sorted order, add the corresponding list to the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n log n). The BFS traversal is O(n). Sorting the column keys is O(k log k) where k is the number of distinct columns. In the worst case (skewed tree), k = n, making the sort O(n log n).
- Space Complexity: O(n). The hash map stores all n node values. The BFS queue holds nodes from at most two adjacent levels, which is O(n) for a complete tree (the widest level has about n/2 nodes).
The bottleneck is the sorting step: the traversal is O(n), and the key sort pushes the total to O(n log n). The next approach removes the sort by tracking the minimum and maximum column indices during the traversal.
Approach 2: BFS + HashMap + Min/Max Column Tracking (Optimal)
Intuition
This builds on Approach 1 with one change. Instead of sorting column keys after the traversal, we track the minimum and maximum column indices as we go. When the BFS finishes, we iterate from minCol to maxCol and collect each column's list, which visits the columns in left-to-right order without a sort.
The final loop reads every column from minCol to maxCol and assumes none of them is empty. This holds because each edge changes the column by exactly 1: the root-to-node path for a node at minCol passes through every column between 0 and minCol, and the same argument applies to maxCol. The occupied columns therefore form a contiguous range of integers.
The per-column order comes from the BFS queue. Parents leave the queue in left-to-right order within a level, and each parent enqueues its left child before its right child, so every level enters the queue in left-to-right order. Each column's list receives nodes top to bottom, with same-row ties resolved left to right.
Algorithm
- If the root is null, return an empty list.
- Create a hash map to store column index to list of node values.
- Initialize
minCol = 0andmaxCol = 0. - Create a BFS queue. Enqueue the root with column index 0.
- While the queue is not empty:
- Dequeue a node and its column index.
- Add the node's value to the hash map entry for that column.
- Update
minCol = min(minCol, column)andmaxCol = max(maxCol, column). - If the node has a left child, enqueue it with column index
column - 1. - If the node has a right child, enqueue it with column index
column + 1. - Iterate from
minColtomaxCol. For each column, add the corresponding list to the result. - Return the result.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We visit every node exactly once during BFS, doing O(1) work per node. Building the result iterates over at most n columns. Total: O(n).
- Space Complexity: O(n). The hash map stores all n node values. The BFS queue holds nodes from at most two adjacent levels, which is O(n) for a complete tree (the widest level has about n/2 nodes).
Approach 2 is optimal at O(n). DFS can also solve the problem, but it needs extra bookkeeping because it does not visit nodes in level order.
Approach 3: DFS + HashMap + Sorting
Intuition
DFS goes deep before going wide, so values do not arrive in top-to-bottom order within a column. A node deep in the left subtree can be recorded before a shallower node in the same column from the right subtree.
The fix is to track each node's row (depth) in addition to its column and store (row, value) pairs in each column's list. After the traversal, sorting each column's list by row restores the top-to-bottom order. The same-row tie-break comes from the traversal order: pre-order DFS finishes the entire left subtree before entering the right subtree at every branch, so two nodes with equal row and column are appended in left-to-right order, and a stable sort by row preserves that order.
Algorithm
- If the root is null, return an empty list.
- Create a hash map to store column index to list of
(row, value)pairs. - Run DFS from the root with initial row 0 and column 0.
- At each node, add
(row, node.val)to the hash map for the current column. - Recursively visit the left child with
(row + 1, column - 1)and the right child with(row + 1, column + 1). - Sort the hash map keys to get column order.
- For each column, sort the entries by row (stable sort preserves left-to-right order for same-row nodes).
- Extract the values, dropping the rows, and add each column's list to the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n log n). DFS visits every node once: O(n). Sorting column keys and entries within each column: O(n log n) in the worst case.
- Space Complexity: O(n). The hash map stores all n entries with row and value. The recursion stack uses O(h) space where h is the tree height (O(n) worst case for a skewed tree).