Vertical Order Traversal of a Binary Tree
HardPrompt
Given the root of a binary tree, calculate the vertical order traversal of the binary tree.
For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).
The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
Return the vertical order traversal of the binary tree.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.Example 2:
Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
1 is at the top, so it comes first.
5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.Example 3:
Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. 0 <= Node.val <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves two main phases. First, we traverse the entire tree using a Depth-First Search (DFS) to determine the coordinates (row, col) and value for each node. We store this information for every node in a list. After the traversal, we sort this list based on the problem's criteria: first by column, then by row, and finally by value for nodes at the same position. Once sorted, we iterate through the list and group the nodes by their column index to construct the final result.
Algorithm
- Create a list, say
nodeInfos, to store custom objects or tuples representing(column, row, value)for each node. - Define a recursive DFS function,
dfs(node, row, col). - Start the traversal from the root:
dfs(root, 0, 0). - Inside the
dfsfunction:- If the current node is
null, return. - Add a new entry
(col, row, node.val)to thenodeInfoslist. - Recursively call for the left child:
dfs(node.left, row + 1, col - 1). - Recursively call for the right child:
dfs(node.right, row + 1, col + 1).
- If the current node is
- After the DFS traversal completes, sort the
nodeInfoslist using a custom comparator. The comparator should compare elements first by column, then by row, and finally by value. - Initialize an empty result list of lists,
verticalOrder. - Iterate through the sorted
nodeInfoslist. Group nodes with the same column index into a temporary list. When the column index changes, add the temporary list toverticalOrderand start a new one. - Return
verticalOrder.
Walkthrough
Algorithm
- Create a list, say
nodeInfos, to store custom objects or tuples representing(column, row, value)for each node. - Define a recursive DFS function,
dfs(node, row, col). - Start the traversal from the root:
dfs(root, 0, 0). - Inside the
dfsfunction:- If the current node is
null, return. - Add a new entry
(col, row, node.val)to thenodeInfoslist. - Recursively call for the left child:
dfs(node.left, row + 1, col - 1). - Recursively call for the right child:
dfs(node.right, row + 1, col + 1).
- If the current node is
- After the DFS traversal completes, sort the
nodeInfoslist using a custom comparator. The comparator should compare elements first by column, then by row, and finally by value. - Initialize an empty result list of lists,
verticalOrder. - Iterate through the sorted
nodeInfoslist. Group nodes with the same column index into a temporary list. When the column index changes, add the temporary list toverticalOrderand start a new one. - Return
verticalOrder.
Code Snippet
class Solution { // A custom class to store node information class NodeInfo { int col, row, val; NodeInfo(int col, int row, int val) { this.col = col; this.row = row; this.val = val; } } List<NodeInfo> nodeInfos = new ArrayList<>(); public List<List<Integer>> verticalTraversal(TreeNode root) { if (root == null) { return new ArrayList<>(); } // 1. Traverse the tree to get coordinates for each node dfs(root, 0, 0); // 2. Sort the list of nodes Collections.sort(nodeInfos, (a, b) -> { if (a.col != b.col) { return a.col - b.col; } if (a.row != b.row) { return a.row - b.row; } return a.val - b.val; }); // 3. Group sorted nodes by column List<List<Integer>> result = new ArrayList<>(); if (nodeInfos.isEmpty()) { return result; } List<Integer> currentColList = new ArrayList<>(); int currentCol = nodeInfos.get(0).col; for (NodeInfo info : nodeInfos) { if (info.col == currentCol) { currentColList.add(info.val); } else { result.add(currentColList); currentCol = info.col; currentColList = new ArrayList<>(); currentColList.add(info.val); } } result.add(currentColList); // Add the last column return result; } private void dfs(TreeNode node, int row, int col) { if (node == null) { return; } nodeInfos.add(new NodeInfo(col, row, node.val)); dfs(node.left, row + 1, col - 1); dfs(node.right, row + 1, col + 1); }}Complexity
Time
O(N log N). The DFS traversal takes O(N) time, where N is the number of nodes. The dominant operation is sorting the list of N nodes, which takes O(N log N) time. Grouping the sorted nodes takes another O(N).
Space
O(N). We need O(N) space for the `nodeInfos` list. The recursion stack for DFS can go up to O(H) where H is the height of the tree, which is O(N) in the worst case of a skewed tree.
Trade-offs
Pros
Relatively straightforward to conceptualize and implement.
Separates the concerns of traversal and sorting.
Cons
Less efficient due to the global sort of all N nodes. It doesn't leverage the partial order (by row) that a level-order traversal might provide.
Requires storing all node information in a flat list before processing, which might not be the most memory-efficient representation.
This approach is more efficient as it builds the sorted result during a single traversal of the tree, avoiding a separate, global sorting step. We use a Breadth-First Search (BFS) traversal and a hierarchy of sorted data structures to maintain the required order. A TreeMap is used to sort columns, a nested TreeMap to sort rows within each column, and a PriorityQueue to sort values for nodes at the same coordinate. By inserting each node's information into this structure during a single BFS pass, we get the correctly grouped and sorted data without a final sorting phase.
Algorithm
- Create a
TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>>to store the nodes. Let's call itcolumnMap. - Create a queue for BFS to store tuples of
(TreeNode, row, col). - Initialize the queue with the root node:
queue.add(new Tuple(root, 0, 0)). - While the queue is not empty:
- Dequeue the current tuple
(node, row, col). - Access the
columnMapto place the node's value. UsecomputeIfAbsentto create nested maps and priority queue if they don't exist for the current(col, row). - Add the node's value to the priority queue:
map.computeIfAbsent(...).add(node.val). - If the node has a left child, enqueue it with coordinates
(row + 1, col - 1). - If the node has a right child, enqueue it with coordinates
(row + 1, col + 1).
- Dequeue the current tuple
- After the BFS is complete, the
columnMapcontains all the information, fully sorted. - Iterate through the
columnMapto construct the final result list.- For each entry in the outer map (each column), create a new list.
- Iterate through the inner map (each row in that column).
- Drain the
PriorityQueuefor that(col, row)and add its elements to the column's list. - Add the completed column list to the final result.
- Return the result.
Walkthrough
Algorithm
- Create a
TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>>to store the nodes. The outer key is the column, the inner key is the row, and thePriorityQueuestores node values. - Create a queue for BFS. The queue will store tuples of
(TreeNode, row, col). - Initialize the queue with the root node:
queue.add(new Tuple(root, 0, 0)). - While the queue is not empty:
- Dequeue the current tuple
(node, row, col). - Access the map to place the node's value. Use
computeIfAbsentto create the nested maps and priority queue if they don't exist for the current(col, row). columnMap.computeIfAbsent(col, k -> new TreeMap<>()).computeIfAbsent(row, k -> new PriorityQueue<>()).add(node.val);- If the node has a left child, enqueue it with coordinates
(row + 1, col - 1). - If the node has a right child, enqueue it with coordinates
(row + 1, col + 1).
- Dequeue the current tuple
- After the BFS is complete, the map contains all the information, fully sorted.
- Iterate through the map to construct the final result list.
- For each entry in the outer map (each column), create a new list.
- Iterate through the inner map (each row in that column).
- Drain the
PriorityQueuefor that(col, row)and add its elements to the column's list. - Add the completed column list to the final result.
- Return the result.
Code Snippet
// Helper class for the queueclass Tuple { TreeNode node; int row; int col; Tuple(TreeNode node, int row, int col) { this.node = node; this.row = row; this.col = col; }} class Solution { public List<List<Integer>> verticalTraversal(TreeNode root) { if (root == null) { return new ArrayList<>(); } // TreeMap to maintain column order. Key: col // Value: Another TreeMap to maintain row order. Key: row // Value of inner map: PriorityQueue to sort nodes at same (row, col) by value. TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>(); Queue<Tuple> queue = new LinkedList<>(); queue.offer(new Tuple(root, 0, 0)); while (!queue.isEmpty()) { Tuple tuple = queue.poll(); TreeNode node = tuple.node; int row = tuple.row; int col = tuple.col; map.computeIfAbsent(col, k -> new TreeMap<>()) .computeIfAbsent(row, k -> new PriorityQueue<>()) .offer(node.val); if (node.left != null) { queue.offer(new Tuple(node.left, row + 1, col - 1)); } if (node.right != null) { queue.offer(new Tuple(node.right, row + 1, col + 1)); } } List<List<Integer>> result = new ArrayList<>(); // Iterate through the sorted columns for (TreeMap<Integer, PriorityQueue<Integer>> rows : map.values()) { List<Integer> colList = new ArrayList<>(); // Iterate through the sorted rows for (PriorityQueue<Integer> pq : rows.values()) { // Add all values from the priority queue (which are sorted) while (!pq.isEmpty()) { colList.add(pq.poll()); } } result.add(colList); } return result; }}Complexity
Time
O(N log N). For each of the N nodes, we perform insertions into the nested data structure. The `TreeMap` operations take `O(log K)` (where K is the number of columns) and the `PriorityQueue` operation takes `O(log S)` (where S is the number of nodes at the same coordinate). This leads to an `O(log N)` operation for each node. Thus, the total time complexity is O(N log N).
Space
O(N). The `TreeMap` structure stores information for all N nodes. The BFS queue can hold up to O(W) nodes, where W is the maximum width of the tree, which is O(N) in the worst case.
Trade-offs
Pros
More elegant design that integrates sorting into the traversal.
Avoids a separate, large sorting step, which can be more efficient on average.
The use of
TreeMapandPriorityQueuedirectly enforces the problem's sorting rules.
Cons
The nested data structure can be more complex to reason about.
The constant factors associated with
TreeMapandPriorityQueueoperations might be higher than a simpleArrayListandCollections.sort().
Solutions
Solution
class Solution {public List<List<Integer>> verticalTraversal(TreeNode root) { List<int[]> list = new ArrayList<>(); dfs(root, 0, 0, list); list.sort(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]); if (o1[1] != o2[1]) return Integer.compare(o2[1], o1[1]); return Integer.compare(o1[2], o2[2]); } }); List<List<Integer>> res = new ArrayList<>(); int preX = 1; for (int[] cur : list) { if (preX != cur[0]) { res.add(new ArrayList<>()); preX = cur[0]; } res.get(res.size() - 1).add(cur[2]); } return res; }private void dfs(TreeNode root, int x, int y, List<int[]> list) { if (root == null) { return; } list.add(new int[]{x, y, root.val}); dfs(root.left, x - 1, y - 1, list); dfs(root.right, x + 1, y - 1, list); }}/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < vector < int >> verticalTraversal ( TreeNode * root ) { vector < tuple < int , int , int >> nodes ; function < void ( TreeNode * , int , int ) > dfs = [ & ]( TreeNode * root , int i , int j ) { if ( ! root ) { return ; } nodes . emplace_back ( j , i , root -> val ); dfs ( root -> left , i + 1 , j - 1 ); dfs ( root -> right , i + 1 , j + 1 ); }; dfs ( root , 0 , 0 ); sort ( nodes . begin (), nodes . end ()); vector < vector < int >> ans ; int prev = - 2000 ; for ( auto [ j , _ , val ] : nodes ) { if ( j != prev ) { prev = j ; ans . emplace_back (); } ans . back (). push_back ( val ); } return ans ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def verticalTraversal ( self , root : TreeNode ) -> List [ List [ int ]]: def dfs ( root , i , j ): if root is None : return nodes . append (( i , j , root . val )) dfs ( root . left , i + 1 , j - 1 ) dfs ( root . right , i + 1 , j + 1 ) nodes = [] dfs ( root , 0 , 0 ) nodes . sort ( key = lambda x : ( x [ 1 ], x [ 0 ], x [ 2 ])) ans = [] prev = - 2000 for i , j , v in nodes : if prev != j : ans . append ([]) prev = j ans [ - 1 ]. append ( v ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.