Tree Traversal

Level-order (BFS)

What is Level-order Traversal?

Level-order traversal visits a tree one depth level at a time — every node at depth 0 (the root), then every node at depth 1, then every node at depth 2, and so on, left to right within each level. It's also called Breadth-First Search (BFS) on a tree, and unlike pre-order, in-order, and post-order, it isn't defined recursively — it's naturally iterative, built around a queue instead of the call stack.

How Does It Work?

The algorithm starts by enqueueing the root. Then it repeatedly dequeues the front node, visits it, and enqueues that node's children (left, then right). Because a queue is FIFO, nodes come back out in exactly the order they were discovered — which guarantees an entire level finishes before the next one starts.

  1. Enqueue the root, 8. Queue: [8]
  2. Dequeue 8, visit it, enqueue its children 3 and 10. Queue: [3, 10]
  3. Dequeue 3, visit it, enqueue its children 1 and 6. Queue: [10, 1, 6]
  4. Dequeue 10, visit it — it has no children. Queue: [1, 6]
  5. Dequeue 1, visit it — it has no children. Queue: [6]
  6. Dequeue 6, visit it — it has no children. Queue is now empty, traversal ends
  7. Final sequence: [8, 3, 10, 1, 6] — notice level 0, then all of level 1, then all of level 2
81321031465
Visit orderNode

This queue-driven, level-by-level structure is why BFS is the traversal used whenever "closer" needs to mean something concrete: finding the shortest path in an unweighted tree/graph, computing a node's minimum depth, or serializing a tree in a way that's easy to reconstruct row by row (e.g. printing a tree layer by layer for display).

Algorithm Steps

  1. If the root is null, return immediately — there's nothing to traverse
  2. Create a queue and enqueue the root
  3. While the queue isn't empty, repeat:
    • Dequeue the front node and visit it
    • If it has a left child, enqueue it
    • If it has a right child, enqueue it

Time Complexity

  • Time Complexity: Every node is enqueued and dequeued exactly once → O(n).
  • Space Complexity: The queue can hold up to a full level's worth of nodes → O(w), up to O(n) worst case.

Time Complexity Analysis

Advertisement

Level-order needs O(w) extra space for the queue, where w is the maximum width of the tree (the largest number of nodes at any single level) — this can be as large as O(n) for a wide, shallow tree, unlike the O(h) stack space used by the recursive DFS traversals.

Daily DSA Challenge by Scale Engineer

Build a tree, then watch level-order (BFS) drain a queue level by level

Tree is empty
No tree yet — insert a value or generate a random tree
Queue (front → back)
empty
Not yet visitedVisitedCurrently dequeuedWaiting in queue

Test Your Knowledge before moving forward!

Level-order Traversal Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Level-order Traversal Implementation

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Level-order traversal (BFS): visit level by level using a queue
function levelOrder(root) {
  const result = [];
  if (root === null) return result;

  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift(); // dequeue the front node

    result.push(node.value);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

// Usage example
let root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);

console.log(levelOrder(root)); // [8, 3, 10, 1, 6]

Done With the Learning

Mark Level-order Traversal as done and view it on your dashboard

Explore Other Tree Topics

Pre-order Traversal

In-order Traversal

Post-order Traversal

Morris Traversal

BST Insertion