Explore level by level using a queue: everything one step away, then everything two steps away, and so on.
Used for
queue: 7
queue: 9, 11
queue: 5, 2
The queue is [9, 11]. Which node is visited next?
Not quite. A queue serves the oldest entry first. 9 was added before 11. (A stack would give 11 first, which is what depth-first search does.)
Step 1 of 5
Goal: find the fewest steps from the start to everything else. Breadth-first search explores in rings: everything one step away, then everything two steps away. It uses a queue, a line where the first one in is the first one out.
Step 2 of 5
Take 7 out and add its children to the back of the line. Both are one step from the start.
Step 3 of 5
Take 9 out and add its children. Take 11 out: nothing to add. 5 and 2 are two steps away.
Step 4 of 5
Nodes are visited ring by ring, so the first time you reach a node is by the shortest route. That is why breadth-first search finds shortest paths when every step costs the same.
Step 5 of 5
Your turn.
QueueBreadth-First Search (graph)Breadth-First Search (tree)
function levelOrder(root) { const out = [], q = root ? [root] : []; while (q.length) { const level = []; for (let n = q.length; n > 0; n--) { const node = q.shift(); level.push(node.val); node.left && q.push(node.left); node.right && q.push(node.right); } out.push(level); } return out;}