Vertical Order Traversal
Given the root of a binary tree, return the vertical order traversal of its nodes’ values.
Constraints:
- The number of nodes in the tree is in the range [1, 100].
- 0 <= Node.val <= 100
Examples:
Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: The tree is: 3 / \ 9 20 / \ 15 7 The vertical order traversal is: 9 / \ 3 15 / \ 20 7
Solutions
Breadth-First Search (BFS)
Time: O(N)Space: O(N)
We use a queue to perform a breadth-first search (BFS) traversal of the tree. For each node, we also keep track of its column number. We use a map to store the nodes at each column. Finally, we construct the result by iterating over the columns in order.
from collections import deque, defaultdict
def verticalTraversal(root):
queue, columnTable = deque([(root, 0)]), defaultdict(list)
min_column, max_column = 0, 0
while queue:
node, column = queue.popleft()
if node is not None:
columnTable[column].append(node.val)
min_column, max_column = min(min_column, column), max(max_column, column)
queue.append((node.left, column - 1))
queue.append((node.right, column + 1))
return [columnTable[x] for x in range(min_column, max_column + 1)]Follow-up:
How would you modify the solution to handle the case where the tree is very large and does not fit in memory?
