Level-order traversal

O(n)

Level-order traversal walks the tree breadth-first: it visits the root, then every node one level down, then the next level, and so on. It uses a queue (dequeue a node, enqueue its children) rather than recursion, and it's how you print a tree level by level or find the shallowest node.

Binary search tree
Press ▶ to run
Edit the input and press Play

How it works

  1. Put the root in a queue.
  2. Dequeue a node and visit it.
  3. Enqueue its left then right child.
  4. Repeat until the queue is empty — nodes come out level by level.

Pseudocode

1levelOrder(root):                   # O(n)2  queue ← [root]3  while queue is not empty:4    node ← queue.dequeue()5    visit(node)6    enqueue node.left, node.right     # next level