How Level-Order Traversal Works
Level-order traversal reads a tree row by row using a queue instead of a stack. It is breadth-first search on a tree, and the only traversal that shows you the tree's shape as you go.
Nothing yet.
- Not reached
- On the stack
- Current
- Visited
Level-order walk over 7 values, 3 levels deep.
Counters
- Visited
- 0/7
- In the queue
- 0
- Tree height
- 3
- Nodes
- 7
Settings
More options
Level-order
- 1
queue = [root] - 2
while queue: - 3
node = queue.shift() - 4
visit(node) - 5
enqueue node.left - 6
enqueue node.right
What each walk is for
| Walk | What you get | Time | Extra space |
|---|---|---|---|
| In-order | Values in sorted order | O(n) | O(h) |
| Pre-order | Root before children, for copying a tree | O(n) | O(h) |
| Post-order | Children before root, for freeing or evaluating | O(n) | O(h) |
| Level-order | Shallowest nodes first, level by level | O(n) | O(w) |
| Search | One value, by comparing at each node | O(h) | O(1) |
Scroll the table sideways for the rest of the columns.
n is the number of values, h the height of the tree and w its widest level. Build the tree from sorted values and h grows all the way to n, which is what balancing prevents.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n) | O(n) | O(n) | O(w) |
How level-order traversal works
Level-order traversal pushes the root into a queue, then repeatedly takes a node off the front, visits it, and pushes its children onto the back. Because the queue is FIFO, everything at depth d comes out before anything at depth d+1. Swapping that queue for a stack turns the same loop into a depth-first walk. The container is the only difference between the two, which is the cleanest way to see what BFS and DFS actually are.
- Put the root in a queue.
- Take the node at the front and visit it.
- Push its left child, then its right child, onto the back of the queue.
- Repeat until the queue is empty.
- To group output by level, record the queue's length before each round. That is exactly the size of the current level.
Implementation
function levelOrder(root) {
if (!root) return [];
const out = [];
let queue = [root];
while (queue.length > 0) {
// One pass per level: the current queue *is* the level.
const next = [];
for (const node of queue) {
out.push(node.value);
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
queue = next;
}
return out;
}When to use it
- Use it to find the shallowest node matching something: the first match found is the closest to the root.
- Use it to print or render a tree by row, and to compute its width or per-level statistics.
- Use it to measure height iteratively, without recursion, by counting rounds.
- Avoid it on very wide trees if memory is tight. The queue holds an entire level at once.