Breadth-First Traversal

Breadth-first search (BFS) on a tree visits nodes in level order — all nodes at depth 0 (the root), then all at depth 1, then depth 2, and so on. A queue (first-in, first-out) is the natural data structure because each node enqueues its children, and children are processed in the order they were enqueued.

Basic Level-Order Traversal

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length) {
    const node = queue.shift();   // dequeue front
    result.push(node.val);
    if (node.left)  queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

// Tree:    1
//         / \
//        2   3
//       / \
//      4   5
//
// levelOrder(root) => [1, 2, 3, 4, 5]

queue.shift() is O(n) for a plain array. For performance-critical code use a proper deque (or a pointer-based queue), but for interview problems shift is fine.

Level-by-Level Grouping

Many problems ask for output grouped by level — for example “right side view”, “level averages”, or “zigzag order”. Capture the queue length at the start of each iteration to process exactly one level per outer-loop pass:

function levelOrderGrouped(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length) {
    const levelSize = queue.length;  // snapshot: nodes at this level
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

// levelOrderGrouped(root) => [[1], [2, 3], [4, 5]]

BFS vs DFS

BFS explores the “frontier” outward uniformly, which is why it finds the shortest path in an unweighted graph. In a tree there is only one path to any node, so BFS and DFS both reach every node; the difference is the order in which they do so.

Practical Pattern: Right Side View

The right-side-view problem (return the last node visible at each level) is a one-liner on top of the grouped pattern: take level[level.length - 1] from each group.

function rightSideView(root) {
  return levelOrderGrouped(root).map(level => level[level.length - 1]);
}

Up Next

Level order is the gateway to the most important specialization of binary trees: the binary search tree, which enforces an ordering property that makes search, insert, and delete all O(h).