Algorithms from zero
Level-order traversal (BFS)
You know three ways to walk a tree recursively—pre-order, in-order, post-order—all exploring deeply down one branch before coming back. But what if you need to see all nodes at depth 2 before any at depth 3? What if you need nodes grouped by level? The depth-first traversals cannot answer that. You need breadth-first search: a queue-based traversal that visits nodes level by level, left to right, from the root down. This is level-order traversal, and it unlocks problems where the position and depth of each node matter.
After this lesson you can implement level-order traversal using a queue, trace the algorithm on a concrete tree, explain why a queue produces level order while recursion produces depth order, implement the “process one level at a time” variant by tracking queue size, and choose level-order traversal for problems that need to understand the tree layer by layer.
What is level-order traversal?
Level-order traversal (also called breadth-first search or BFS) visits every node in a tree layer by layer, top to bottom, left to right. Unlike the recursive depth-first traversals you saw in the last lesson, level-order uses a queue—a first-in, first-out container—to control the visiting order.
Why a queue produces level order
The magic of level-order is the queue’s FIFO property. When you process a node and add its children to the queue, the children go to the back of the queue. All nodes at the current level are still in the queue, ahead of their children. So you process all nodes at level 1, then all at level 2, and so on—you never skip ahead to a deeper level until the current level is exhausted.
Contrast this with recursion: when you call preOrder(node.left), you immediately dive deep into the left subtree before ever seeing the right child. Recursion is depth-first. A queue is breadth-first.
The basic level-order loop
- Create a queue and add the root.
- While the queue is not empty:
- Dequeue a node.
- Process it (record its value).
- Enqueue its left child (if it exists).
- Enqueue its right child (if it exists).
- Done.
Processing one level at a time
Often you want to group nodes by level—all level-1 nodes together, all level-2 nodes together. The trick: at the start of each level, record the queue’s size. That number tells you exactly how many nodes are at the current level. Iterate that many times, dequeuing and enqueueing children. When you’ve iterated size times, all the children (the next level) are now in the queue, and you loop again.
This variant is essential for problems like “return the level order traversal as a list of lists” or “find the width of each level.”
Basic level-order traversal
The simplest form: enqueue the root, then dequeue, process, and enqueue children until the queue is empty.
1
function levelOrder(root) {
2
if (root === null) return [];
3
4
const result = [];
5
const queue = [root]; // Start with the root
6
7
while (queue.length > 0) {
8
const node = queue.shift(); // Dequeue from the front
9
10
// Process the node
11
result.push(node.value);
12
13
// Enqueue children
14
if (node.left !== null) queue.push(node.left);
15
if (node.right !== null) queue.push(node.right);
16
}
17
18
return result;
19
}
- L1 Function takes the root of the tree.
- L2 If the tree is empty (null root), return an empty result.
- L5 Use an array as a queue. Start with the root.
- L7 Loop until the queue is empty.
- L8 Dequeue (remove) the front node.
- L11 Process the node: record its value.
- L14 Enqueue the left child if it exists.
- L15 Enqueue the right child if it exists.
- L18 Return the result: nodes in level-order.
Example: For the tree:
1
/ \
2 3
/
4Level-order visits in this order: 1 → 2 → 3 → 4.
Level-order with grouping (one level at a time)
To return nodes grouped by level, capture the queue’s size at the start of each iteration. That size is the count of nodes at the current level.
1
function levelOrderByLevel(root) {
2
if (root === null) return [];
3
4
const result = [];
5
const queue = [root];
6
7
while (queue.length > 0) {
8
const levelSize = queue.length; // How many nodes at this level
9
const currentLevel = []; // Nodes of this level
10
11
// Process all nodes at the current level
12
for (let i = 0; i < levelSize; i++) {
13
const node = queue.shift(); // Dequeue from the front
14
currentLevel.push(node.value); // Record the node's value
15
16
// Enqueue children for the next level
17
if (node.left !== null) queue.push(node.left);
18
if (node.right !== null) queue.push(node.right);
19
}
20
21
// After processing levelSize nodes, the queue now holds only the next level
22
result.push(currentLevel);
23
}
24
25
return result;
26
}
- L1 Function returns a list of lists: each inner list is one level.
- L2 If the tree is empty, return an empty result.
- L5 Use an array as a queue. Start with the root.
- L7 Loop while the queue is not empty.
- L8 Capture the queue's size—this is the count of nodes at the current level.
- L11 For loop from 0 to levelSize: process exactly that many nodes.
- L12 Dequeue a node from the front.
- L13 Record its value in the current level's list.
- L16 Enqueue its children; they will be processed in the next iteration.
- L20 After the for loop, add the current level's nodes to the result.
Example: For the same tree:
1
/ \
2 3
/
4Result: [[1], [2, 3], [4]]—each level as a separate list.
Running both on a concrete tree
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
levelOrder(root);
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
levelOrderByLevel(root);
Time complexity
Level-order traversal visits every node in the tree exactly once. Each node is dequeued once and enqueued once. All work done per node (processing, children checks) is O(1). Therefore, for a tree with n nodes, the time is O(n).
Space complexity
The space used by the queue is the dominant factor. At any moment, the queue holds nodes from at most two consecutive levels. In the worst case, the maximum width of the tree—the largest number of nodes at any single level—determines the queue’s maximum size.
For a tree with maximum width w, the space complexity is O(w).
In a balanced binary tree, w is roughly n / 2 (the last level has many nodes), so O(w) is still better than the O(n) space used by recursion in the worst case. In a skewed tree (where every node has only one child), w = 1, so level-order uses O(1) space—far better than the O(n) recursion stack.
For the tree: 5 / \ 3 7 / \ 2 4 What is the level-order traversal?
Why does a queue produce level-order while recursion produces depth-first?
In the level-order 'by level' variant, what does levelSize represent?
After processing levelSize nodes and enqueueing all their children, what does the queue contain?
For a tree with maximum width w (the most nodes at any level), what is the space complexity of level-order traversal?
lesson.inset.undefined
Why not recursion? Recursion explores depth-first: it goes all the way down the left subtree before exploring the right. If you need to know the level of each node or group nodes by depth, recursion obscures that structure. A queue makes the level structure explicit: dequeue level k, enqueue level k+1.
lesson.inset.undefined
Trace the “by level” variant yourself. Draw a tree with 3 levels. For the level-order ‘by level’ traversal, draw the queue state after each level is processed. Watch how levelSize = queue.length captures the current level’s count. This is the core insight.
lesson.inset.undefined
Empty trees and single nodes. If the root is null, return immediately (empty result). If the tree is a single node, the queue holds just that node, the loop runs once, and you’re done. Both cases are handled by the algorithm without special code.
Why is level-order traversal useful even though both it and depth-first traversals visit all nodes?
Level-order traversal (BFS) visits nodes layer by layer, top to bottom, left to right, using a queue’s FIFO property. Unlike recursive depth-first traversals, level-order makes the tree’s layer structure explicit. The basic algorithm: enqueue the root, loop while the queue is not empty, dequeue and process a node, then enqueue its children. To group nodes by level, capture the queue’s size at the start of each iteration—that number tells you exactly how many nodes are at the current level. Time complexity is O(n) (visit each node once). Space complexity is O(w), where w is the maximum width of the tree—better than O(n) recursion space in many cases. The next lesson covers recursion on trees: solving tree problems by combining results returned from subtrees.