# Vertical Order Traversal of a Binary Tree **Difficulty:** HARD [External](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree) Canonical: https://scaleengineer.com/dsa/problems/vertical-order-traversal-of-a-binary-tree **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search) **Data structures:** Hash Table, Tree, Binary Tree **Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Samsung](https://scaleengineer.com/companies/samsung), [eBay](https://scaleengineer.com/companies/ebay), [Deliveroo](https://scaleengineer.com/companies/deliveroo) --- ## Problem 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:** ![](https://assets.glich.co/dsa/vertical-order-traversal-of-a-binary-tree/image0.jpg) **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:** ![](https://assets.glich.co/dsa/vertical-order-traversal-of-a-binary-tree/image1.jpg) **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:** ![](https://assets.glich.co/dsa/vertical-order-traversal-of-a-binary-tree/image2.jpg) **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 ## DFS with Global Sorting 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. **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. **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. ### Explanation ### Algorithm 1. Create a list, say `nodeInfos`, to store custom objects or tuples representing `(column, row, value)` for each node. 2. Define a recursive DFS function, `dfs(node, row, col)`. 3. Start the traversal from the root: `dfs(root, 0, 0)`. 4. Inside the `dfs` function: * If the current node is `null`, return. * Add a new entry `(col, row, node.val)` to the `nodeInfos` list. * 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)`. 5. After the DFS traversal completes, sort the `nodeInfos` list using a custom comparator. The comparator should compare elements first by column, then by row, and finally by value. 6. Initialize an empty result list of lists, `verticalOrder`. 7. Iterate through the sorted `nodeInfos` list. Group nodes with the same column index into a temporary list. When the column index changes, add the temporary list to `verticalOrder` and start a new one. 8. Return `verticalOrder`. ### Code Snippet ```java 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 nodeInfos = new ArrayList<>(); public List> 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> result = new ArrayList<>(); if (nodeInfos.isEmpty()) { return result; } List 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); } } ``` ### Algorithm 1. Create a list, say `nodeInfos`, to store custom objects or tuples representing `(column, row, value)` for each node. 2. Define a recursive DFS function, `dfs(node, row, col)`. 3. Start the traversal from the root: `dfs(root, 0, 0)`. 4. Inside the `dfs` function: - If the current node is `null`, return. - Add a new entry `(col, row, node.val)` to the `nodeInfos` list. - 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)`. 5. After the DFS traversal completes, sort the `nodeInfos` list using a custom comparator. The comparator should compare elements first by column, then by row, and finally by value. 6. Initialize an empty result list of lists, `verticalOrder`. 7. Iterate through the sorted `nodeInfos` list. Group nodes with the same column index into a temporary list. When the column index changes, add the temporary list to `verticalOrder` and start a new one. 8. Return `verticalOrder`. ## BFS with Ordered Map and Priority Queues 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. **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. **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 `TreeMap` and `PriorityQueue` directly enforces the problem's sorting rules. **Cons:** The nested data structure can be more complex to reason about.; The constant factors associated with `TreeMap` and `PriorityQueue` operations might be higher than a simple `ArrayList` and `Collections.sort()`. ### Explanation ### Algorithm 1. Create a `TreeMap>>` to store the nodes. The outer key is the column, the inner key is the row, and the `PriorityQueue` stores node values. 2. Create a queue for BFS. The queue will store tuples of `(TreeNode, row, col)`. 3. Initialize the queue with the root node: `queue.add(new Tuple(root, 0, 0))`. 4. While the queue is not empty: * Dequeue the current tuple `(node, row, col)`. * Access the map to place the node's value. Use `computeIfAbsent` to 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)`. 5. After the BFS is complete, the map contains all the information, fully sorted. 6. 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 `PriorityQueue` for that `(col, row)` and add its elements to the column's list. * Add the completed column list to the final result. 7. Return the result. ### Code Snippet ```java // Helper class for the queue class 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> 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>> map = new TreeMap<>(); Queue 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> result = new ArrayList<>(); // Iterate through the sorted columns for (TreeMap> rows : map.values()) { List colList = new ArrayList<>(); // Iterate through the sorted rows for (PriorityQueue 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; } } ``` ### Algorithm 1. Create a `TreeMap>>` to store the nodes. Let's call it `columnMap`. 2. Create a queue for BFS to store tuples of `(TreeNode, row, col)`. 3. Initialize the queue with the root node: `queue.add(new Tuple(root, 0, 0))`. 4. While the queue is not empty: - Dequeue the current tuple `(node, row, col)`. - Access the `columnMap` to place the node's value. Use `computeIfAbsent` to 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)`. 5. After the BFS is complete, the `columnMap` contains all the information, fully sorted. 6. Iterate through the `columnMap` 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 `PriorityQueue` for that `(col, row)` and add its elements to the column's list. - Add the completed column list to the final result. 7. Return the result. # Solutions ### Java ```java class Solution { public List> verticalTraversal(TreeNode root) { List list = new ArrayList<>(); dfs(root, 0, 0, list); list.sort(new Comparator() { @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> 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 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); } } ``` ### CPP ```cpp /** * 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 ; } }; ``` ### Python ```python # 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 ans ```