Level-order traversal
Visit the root, then all of its children, then all of theirs, level by level. A queue does the bookkeeping: take a node from the front, visit it, and add its children to the back. They wait behind everything on the level above.
queue: front on the left, back on the right
Visit the tree level by level: the root, then everything one step down, then two steps down, and so on.
1function levelOrder(root) {2 const out = [];3 const queue = root === null ? [] : [root];4 while (queue.length > 0) {5 const node = queue.shift();6 out.push(node.value);7 if (node.left !== null) queue.push(node.left);8 if (node.right !== null) queue.push(node.right);9 }10 return out;11}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | every node goes through the queue once |
| average | n | any shape of tree |
| worst | n | the same for every tree |
| space | w | the widest level waits in the queue: about n / 2 in a full tree |
Where it breaks
- Using a stack by mistake. Swap the queue for a stack and the walk dives down one branch first: a depth-first order, not level by level.
- Wide trees use the most memory. Pick Wide: the whole bottom level, 8 of the 15 nodes, sits in the queue at once. A chain only ever holds one node.
- Knowing where a level ends. To print one line per level, note the queue's length at the start of each level and take exactly that many nodes before moving on.