Medium Trees
Level-order Traversal
Receives an array of integers and interprets it as a binary tree laid out level-order — index i's children live at 2i+1 and 2i+2, the same indexing scheme used by binary heaps. It then walks the tree breadth-first with a queue: starting from the root, each pass drains every node currently in the queue into one result row while enqueuing their children for the next pass. Returns an array of arrays, one per depth level (shallowest first), each holding that level's node values left to right.
Visualization
- Input
- Result
Algorithm code
// Level-order Traversal (BFS) — a single pure function. Interprets the given
// values as a complete binary tree laid out level-order (index i's children
// live at 2i+1 and 2i+2), then walks it breadth-first with a queue of
// indices, grouping each depth's node values into its own array.
/**
* @param {number[]} values - tree nodes in level-order (index i's children are at 2i+1 and 2i+2)
* @returns {number[][]} node values grouped by depth level, shallowest first
*/
export function levelOrderTraversal(values) {
if (values.length === 0) {
return [];
}
const levels = [];
let queue = [0];
while (queue.length > 0) {
const level = [];
const nextQueue = [];
for (const index of queue) {
level.push(values[index]);
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < values.length) {
nextQueue.push(left);
}
if (right < values.length) {
nextQueue.push(right);
}
}
levels.push(level);
queue = nextQueue;
}
return levels;
}FUNCTION levelOrderTraversal(values):
IF LENGTH(values) = 0:
RETURN []
levels ← []
queue ← [0]
WHILE LENGTH(queue) > 0:
level ← []
nextQueue ← []
FOR EACH index IN queue:
APPEND values[index] TO level
left ← 2 * index + 1
right ← 2 * index + 2
IF left < LENGTH(values):
APPEND left TO nextQueue
IF right < LENGTH(values):
APPEND right TO nextQueue
APPEND level TO levels
queue ← nextQueue
RETURN levels