Sponsored
Sponsored
This 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.
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.
1from collections import defaultdict, deque
2
3def verticalOrderTraversal(root):
4 if not root:
5 return []
6
7 col_table = defaultdict(list)
8 min_col = max_col = 0
9 queue = deque([(root, 0, 0)]) # node, row, column
10
11 while queue:
12 node, row, col = queue.popleft()
13 if node:
14 col_table[col].append((row, node.val))
15 min_col = min(min_col, col)
16 max_col = max(max_col, col)
17 queue.append((node.left, row + 1, col - 1))
18 queue.append((node.right, row + 1, col + 1))
19
20 result = []
21 for col in range(min_col, max_col + 1):
22 # Sort by row and then by value
23 col_table[col].sort(key=lambda x: (x[0], x[1]))
24 result.append([val for row, val in col_table[col]])
25
26 return resultWe 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.
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.
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.
1def verticalOrderTraversal(root):
2 node_list =
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.