ENDEAR
Start free
algorithmpro

Breadth-first tree traversal

Visit a tree level by level, using a queue to remember which node comes next.

time
O(n)
space
O(n)

// step through it

step 1 / 15
1function levelOrder(root) {2  const queue = [root], out = [];3  while (queue.length > 0) {4    const node = queue.shift();5    out.push(node.val);6    if (node.left) queue.push(node.left);7    if (node.right) queue.push(node.right);8  }9  return out;10}
queue
= [4]
out
= []
4261357
  • 4
  • 2
  • 6
  • 1
  • 3
  • 5
  • 7

Put the root, 4, in the queue.

// pro lesson

Unlock the full walkthrough

This lesson is part of Pro. Pro unlocks every step of every lesson, plus pattern drills and mastery insights.

See pricing

How it works

Breadth-first search visits every node on one level before moving down. A queue keeps the order: take the node at the front, output it, and add its children at the back. Children always join behind everything already waiting, so a whole level is finished before the next one starts. The same idea finds the shortest path in an unweighted graph. O(n) time, and O(n) space for the queue.

Practice spotting this pattern →