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:
[1, 1000].0 <= Node.val <= 1000This approach uses a Breadth-First Search (BFS) to traverse the tree while tracking each node's position (row, col). We use a queue to manage our BFS process, which stores tuples of (node, row, col). As we visit each node, we place it into a list corresponding to its column index. Finally, we sort each column by first row, then value, and construct the result.
We initialize a queue for BFS, starting with the root node at position (0, 0). For each node processed, we record its value in a list corresponding to its column index and adjust column bounds.
Finally, for each column, we sort the nodes first by their row and then by value, assembling the output in column order. This efficiently manages the node organization for vertical traversal.
Java
C++
Time Complexity: O(N log N) due to sorting, where N is the number of nodes.
Space Complexity: O(N) for the storage of node values, where N is the number of nodes.
This method involves performing a pre-order traversal (DFS) to collect all nodes along with their column and row indices. Once collected, nodes are sorted based on their columns first, then their rows, and finally their values. The sorted list is then grouped into lists according to their column indices to produce the final vertical order traversal.
The DFS collects nodes with their positions into a list. This unsorted list is then sorted by column, row, and value. Finally, nodes are classified into their corresponding columns based on sorted order.
This approach relies on sorting all nodes at the end to define their order in the result.
Java
Time Complexity: O(N log N) due to sorting, where N is the total number of nodes.
Space Complexity: O(N) to store all the nodes along with their positions.
| Approach | Complexity |
|---|---|
| Approach 1: BFS with Coordinate Tracking | Time Complexity: O(N log N) due to sorting, where N is the number of nodes. Space Complexity: O(N) for the storage of node values, where N is the number of nodes. |
| Approach 2: DFS with Sorting | Time Complexity: O(N log N) due to sorting, where N is the total number of nodes. Space Complexity: O(N) to store all the nodes along with their positions. |
L21. Vertical Order Traversal of Binary Tree | C++ | Java • take U forward • 390,784 views views
Watch 9 more video solutions →Practice Vertical Order Traversal of a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode