Pattern Guide
Tree Level-Order Variants
"BFS tree traversals: zigzag, right side view, level averages, cousins."
Level-order (BFS) traversal processes a tree level by level. Variants: zigzag (alternate left-right and right-left), right side view (last node of each level), level averages, level maximum, cousins check (same level, different parents), vertical order traversal, and boundary traversal. All share the same BFS template with slight modifications per level.
Problems you can solve with this pattern
4 problems · click any to start solving
// Generic level-order BFS template
function levelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
while (queue.length) {
const level = [];
const size = queue.length; // snapshot size for this level
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}
// Zigzag: reverse alternate levels
function zigzagLevelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
let leftToRight = true;
while (queue.length) {
const size = queue.length, level = [];
for (let i = 0; i < size; i++) {
const node = queue.shift();
leftToRight ? level.push(node.val) : level.unshift(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
leftToRight = !leftToRight;
}
return result;
}BFS template: queue=[root], process level by level (snapshot queue size each level). Right side view: take last node of each level. Zigzag: alternate direction each level (reverse odd levels). Level averages: sum / count per level. Vertical order: group by column offset (left child = col-1, right child = col+1). All these variations touch the same BFS code with different collection logic.
// Generic level-order BFS template
function levelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
while (queue.length) {
const level = [];
const size = queue.length; // snapshot size for this level
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}
// Zigzag: reverse alternate levels
function zigzagLevelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
let leftToRight = true;
while (queue.length) {
const size = queue.length, level = [];
for (let i = 0; i < size; i++) {
const node = queue.shift();
leftToRight ? level.push(node.val) : level.unshift(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
leftToRight = !leftToRight;
}
return result;
}Level-order variations:
- Right side view: result.push(level[level.length-1])
- Zigzag: toggle push vs unshift, or use direction flag
- Averages: sum/count per level
- Maximum: Math.max(...level)
- Connect next right pointers: directly connect nodes within level loop
DFS alternative for right side view: DFS tracking depth; if depth == result.length, add to result (first visit = leftmost). For right side view, process right before left.