314. Binary Tree Vertical Order Traversal - Detailed Explanation
Problem Statement
Binary Tree Vertical Order Traversal: Given the root of a binary tree, return the vertical order traversal of its nodes' values – i.e. values grouped by vertical column from leftmost column to rightmost column, top to bottom within each column. If two nodes are in the same column and same row (depth), they should appear in left-to-right order in the output.
- Constraints: The number of nodes is up to 100, and node values range from -100 to 100. An empty tree should return an empty list.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: The tree has root 3, left child 9 and right subtree with 20 (whose children are 15 and 7). The leftmost vertical column contains only 9. The next column contains 3 (above) and 15 (below). Then 20 alone in the next column, and 7 in the rightmost column. So the vertical order is [[9], [3,15], [20], [7]].
Example 2:
Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]
Explanation: This tree’s vertical columns are: leftmost has 4, next has 9, middle has 3, 0, 1 (all in the same column with 3 higher up), then 8, and rightmost has 7. Notice nodes 0 and 1 are in the same row and column – since 0 is encountered from the left side and 1 from the right, 0 comes before 1 in that sublist.
Example 3:
Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]
Explanation: The tree is larger. Vertically from left to right: [4] (leftmost column); [9,5] (next column, 9 above 5); [3,0,1] (middle column, with 3 on top, and 0 and 1 at the same depth listed left-to-right); [8,2] (next column, 8 above 2); [7] (rightmost column).
Hints
- Horizontal Distance as Column Index: Assign a “column index” (horizontal distance from the root) to each node. For example, root at column 0, left child at column -1, right child at column +1, and so on. Nodes with the same column index line up vertically.
- Use a Data Structure to Group Columns: Consider using a hash map or dictionary to collect nodes for each column index. You’ll need to traverse the tree and fill this map.
- Traversal Order Matters: A breadth-first traversal (level-order) naturally visits nodes top-down and left-to-right, which helps maintain the required order. A depth-first traversal can be used too, but you must record each node’s depth to order nodes vertically.
Approach 1: Brute Force Solution (DFS + Sorting)
Idea: A straightforward (but not most efficient) approach is to assign coordinates to every node and then sort by those coordinates. We can perform a DFS traversal to record each node’s column index (horizontal distance) and depth (vertical level). After collecting all nodes with their coordinates, we sort the list by column first, then by depth. Finally, we group the node values by column. This brute-force approach is easy to implement and understand, though it does extra work by sorting all nodes.
Step-by-Step:
-
DFS Traversal with Coordinates: Start a depth-first search from the root (coordinate
(col=0, row=0)). For each node, if you go left, decrement column (col–1) and increment row (row+1); if you go right, increment column (col+1) and increment row. Record each node’s value along with its(col, row)coordinates. -
Collect Nodes: Use a list to collect tuples
(col, row, value)for every node visited. For example, from Example 2, you would collect entries like(0,0,3),(-1,1,9),(1,1,8),(-2,2,4),(0,2,0),(0,2,1),(2,2,7). -
Sort by Column and Row: Sort this list of tuples by column first, and if the column is the same, sort by row (this ensures top-down order). After sorting, the example tuples become
(-2,2,4), (-1,1,9), (0,0,3), (0,2,0), (0,2,1), (1,1,8), (2,2,7). -
Group by Column: Iterate through the sorted list and group values by column. Every time the column index changes, start a new sublist. In the example, this grouping yields column -2:
[4], column -1:[9], column 0:[3, 0, 1], column 1:[8], column 2:[7].
Python Code (DFS + sort):
Java Code (DFS + sort):
Complexity: This brute-force method runs in O(N · log N) time due to sorting all nodes (where N is number of nodes). The DFS traversal itself is O(N), and then sorting the list of size N takes O(N log N). Space complexity is O(N) to store the list of node info and the output. This is acceptable for N up to 100. However, sorting can be unnecessary work – we can do better by leveraging traversal order, as shown next.
Approach 2: BFS-Based Optimal Solution
Idea: We can achieve the vertical order in one pass using breadth-first search (BFS). BFS processes nodes level by level (top-down, left-to-right), which aligns perfectly with the requirement that nodes higher up (smaller row) and, for equal rows, leftmost should come first. We will use a queue to perform BFS and a map to collect nodes by column index as we go. This way, we avoid explicitly sorting by row because BFS inherently visits in the required order. We’ll still need to output columns from leftmost to rightmost, which we can handle by tracking the minimum and maximum column indices seen.
Step-by-Step:
- Initialize: Start with an empty map (column -> list of values) and a queue for BFS. Enqueue the root node with column index 0. Track
min_colandmax_colseen so far (start both at 0). - Level-Order Traversal: While the queue is not empty, pop the front
(node, col)pair. Append the node’s value to the list for its column in the map. Then enqueue the node’s left child withcol-1and right child withcol+1. Updatemin_colandmax_colaccordingly as you go. This processes nodes in order of increasing depth. If two nodes share the same column and depth, the one encountered first in BFS (the left one) will naturally be processed first and added to the list before the other – satisfying left-to-right order for same-row nodes. - Compile Result: After BFS, iterate from
min_coltomax_coland collect the lists of values from the map for each column. This yields the vertical order groups from leftmost column to rightmost. (Columns with no nodes can be skipped, but in a binary tree every column in the range will have at least one node by definition of howmin_col/max_colwere set.)
Python Code (BFS):
Java Code (BFS):
Complexity: BFS touches each node once, so the traversal is O(N). Grouping by column and iterating over the range of columns is also O(N) in total. If we use a sorted structure (like a TreeMap) for columns, that would add a log factor (O(N log N)), but by tracking min_col and max_col we avoid sorting the keys. Space complexity is O(N) for the map and the queue. This approach is efficient – essentially linear in the number of nodes.
Approach 3: DFS-Based Alternative Solution
Idea: We can also solve the problem using depth-first search (DFS) with careful bookkeeping. The challenge with DFS is that it doesn’t naturally preserve the top-to-bottom order if one branch is deeper than another. To handle this, we record each node’s depth (row) in addition to its column, similar to Approach 1. We can use a map to gather nodes by column during the DFS traversal. After the traversal, we sort the nodes in each column by their depth. This achieves the correct vertical ordering. One advantage of DFS is that it can be implemented recursively, which some find easier to reason about. However, remember that we must explicitly handle ordering, whereas BFS did that implicitly.
Step-by-Step:
-
Recursive Traversal: Perform a DFS starting from the root at
(col=0, row=0). When you go left, do(col-1, row+1); when you go right, do(col+1, row+1). Maintain a mapcol -> list of (row, value)for nodes. For each node visited, append(row, value)to the list for that column. -
Collect Data: By the end of DFS, you’ll have a dictionary mapping each column index to a list of
(row, value)pairs. For example, on the tree from Example 2, you might have:- column -2:
[(2, 4)] - column -1:
[(1, 9)] - column 0:
[(0, 3), (2, 0), (2, 1)] - column 1:
[(1, 8)] - column 2:
[(2, 7)]
(The pairs record the depth of each value.)
- column -2:
-
Sort Within Columns: Iterate over each column’s list and sort it by the row value (ascending). This will order the nodes from top to bottom. In our example, the list for column 0
[(0,3), (2,0), (2,1)]when sorted by row becomes[(0,3), (2,0), (2,1)](it was already mostly sorted; if two nodes have the same row, their order in this list reflects the DFS traversal order – left subtree nodes would have been added before right subtree nodes). -
Prepare Output: Traverse the columns in increasing order of their keys (leftmost to rightmost column), and for each column, extract the node values from the sorted list (discard the row info now) and add the list of values to the result.
Comparison with BFS: Both DFS and BFS ultimately produce the same grouping. BFS naturally guarantees the correct vertical order (no additional sorting by depth needed), whereas DFS needs that extra sort by depth because it might visit nodes out of vertical order. For instance, a DFS might go all the way down left then back up and down right – a lower node on the left could be visited before a higher node on the right. We handled this by sorting on depth. In terms of complexity, this DFS approach is also O(N log N) due to sorting steps. The DFS recursion uses the call stack, which in the worst case (skewed tree) can be O(N) deep. BFS uses a queue which in the worst case can hold O(N) nodes at once (for a very bushy tree). So space complexity is similar. The choice often comes down to which traversal logic one finds more straightforward.
Python Code (DFS with map):
Java Code (DFS with map):
Complexity: The DFS traversal itself is O(N). We then sort each column’s list of nodes by row. In the worst case (e.g. a balanced tree), there might be O(N) columns each with a few nodes, or in another worst case (a skewed tree), 1 column with O(N) nodes. Either way, the total sorting across all columns is O(N log N) in the worst scenario. Space complexity is O(N) for the storage of nodes in the map and for the recursion stack.
Pros and Cons: The DFS approach is an alternative when one prefers recursion. It requires careful handling of the vertical ordering (depth sorting) but uses similar space and time overall. The BFS approach is often considered more direct for this particular problem since vertical order is inherently level-oriented. However, DFS gives the flexibility to combine conditions (like if we needed to sort by values as well, which is a variation of this problem). Both approaches are valid as long as ordering is correctly managed.
Step-by-Step Walkthrough and Visual Examples
Above is the binary tree from Example 2. Each vertical dashed line corresponds to a column of the vertical order. The leftmost line goes through node 4, the next through 9, the middle line through 3 (and also 0 and 1 which are directly beneath 3), then one through 8, and the rightmost through 7. Nodes 0 and 1 are drawn overlapping on the same vertical line under 3 – indicating they share the same column. Our goal is to collect nodes column by column.
Let’s walk through the BFS traversal for this example tree:
- Level 0: Visit node
3at column 0. - Level 1: Visit node
9at column -1, then node8at column 1. (We go left to9first, then right to8.) - Level 2: Visit nodes
4at column -2,0at column 0,1at column 0, and7at column 2 – in that order from left to right. Node4comes from the leftmost branch,0is the right child of9,1is the left child of8; both0and1end up in column 0 along with3(which is higher up in that column), and7is in the far right column.
After this traversal, we group nodes by their column index:
- Column -2: [4]
- Column -1: [9]
- Column 0: [3, 0, 1]
- Column 1: [8]
- Column 2: [7]
Reading off these groups from leftmost column to rightmost gives the result [[4],[9],[3,0,1],[8],[7]], which matches the expected output for Example 2. The BFS process naturally ensured that within each column the nodes appear top-down and left-before-right at the same depth. The visual alignment of 0 and 1 under 3 in the diagram corresponds to them sharing the “column 0” list in the output, with 0 preceding 1 because 0 was reached before 1 in the traversal.
Common Mistakes and Edge Cases
-
Forgetting Depth Ordering (DFS): A common pitfall is to use DFS and group nodes by column without considering their depth. This can lead to incorrect ordering. For example, a deeper node in the left subtree might be added before a higher node in the right subtree that belongs in the same column. Always record the depth (row) for each node if you use DFS, and sort or otherwise order by depth before outputting.
-
Not Sorting Columns in Output: If you use an unordered map for collecting columns (as in most languages’ hash map/dict), iterating over its keys can produce columns in arbitrary order. Make sure to sort the column indices or use a data structure (like
TreeMapin Java) to output columns from leftmost to rightmost. -
Left and Right Children Column Calculation: Be careful to decrement the column index for left child and increment for right child. Mixing these up will swap the sides. By definition, left moves you one column to the left (col - 1) and right moves you one to the right (col + 1).
-
Negative Column Indices: It’s okay for column indices to be negative (left side). If using a zero-indexed array or list to store columns, you’ll need to offset the indices. A simpler approach is to use a dictionary or map so that you can use negative keys, or first compute the minimum column index and offset based on that.
-
Empty Tree: Ensure your code handles an empty input (root is
None/null). It should return an empty list[], not a list with one empty sublist. -
Multiple Nodes in Same Column and Row: As demonstrated, if two nodes end up with the same column and depth, the one that appears first in left-to-right order of the tree should come first. BFS naturally handles this. If using DFS, ensure that when depths are equal you preserve the original left-right order (for example, by stable sorting or by processing left subtree before right subtree, which the recursion naturally does).
-
Unbalanced Trees: The approaches above work for skewed or unbalanced trees as well. For extremely skewed trees (like a chain), the vertical order is just the same as the pre-order or level-order traversal. Just make sure your solution doesn’t assume a balanced tree in its logic.
Alternative Variations and Related Problems
Vertical traversal is related to other “views” of binary trees and grid-based traversals:
-
Top View of Binary Tree: This requires printing the first node visible in each vertical column when looking from above. It’s similar to vertical order, but you pick only the top-most node in each column (one per column). This can be done with a BFS that records the first node encountered at each column.
-
Bottom View of Binary Tree: Opposite of top view – take the bottom-most node in each vertical column. You can solve it by a BFS or DFS that continually updates the node seen at each column (so the last one at that column wins).
-
Vertical Order Traversal II (LeetCode 987): A harder variation where if two nodes share the same row and column, you must sort them by their values (instead of relying on left/right order). The approach is similar (assign
colandrow), but after collecting nodes you sort bycol, thenrow, then value. -
Diagonal Traversal of Binary Tree: In a diagonal view, nodes are grouped by lines at 45° to the vertical (for example, root with its right child and right-grandchild might lie on one diagonal). This can be solved by grouping nodes by
row - colorrow + col(depending on definition) instead of bycol. It’s another variant that uses hashing of coordinates.
Related LeetCode problems for practice:
-
LeetCode 987. Vertical Order Traversal of a Binary Tree – Similar to this problem but adds a tie-break by node value when two nodes share position.
-
LeetCode 199. Binary Tree Right Side View – Uses BFS/DFS to capture the “view” from the right side (a different perspective but also about levels and ordering).
-
LeetCode 102. Binary Tree Level Order Traversal – Classic BFS level-by-level (horizontal order instead of vertical). This is simpler but related in that it uses a queue to traverse a tree in structured order.
GET YOUR FREE
Coding Questions Catalog
