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.
const verticalTraversal = (root) => {
const map = new Map();
const queue = [[root, 0]];
let min = 0,
max = 0;
while (queue.length) {
const [node, x] = queue.shift();
if (!node) continue;
if (!map.has(x)) map.set(x, []);
map.get(x).push(node.val);
min = Math.min(min, x);
max = Math.max(max, x);
queue.push([node.left, x - 1]);
queue.push([node.right, x + 1]);
}
const res = [];
for (let i = min; i <= max; i++) {
res.push(map.get(i));
}
return res;
};
Follow-up:
How would you modify the solution to handle the case where the tree is very large and does not fit in memory?
