What does level-order traversal (traversing a tree by levels) do?

AlgorithmsJunior~2 min read

Short answer

Level-order traversal (traversing a tree by levels) visits the tree's nodes layer by layer, from the root to the leaves, left to right, using a queue (BFS). It first visits all nodes at depth 0, then depth 1, then depth 2, and so on.

Detailed explanation

What it does: visits nodes in order of non-decreasing edge distance from the root, grouping them by depth level.
How it works: uses a queue. Take the root, put it in the queue; while the queue isn't empty, pull out the current level (the number of elements equals the queue's current size), and add all of each node's children to the queue in sequence.
Result: you can get either a flat sequence or a list of levels (an array of arrays).
Complexity: time O(n), where n is the number of nodes; memory O(w), where w is the tree's maximum width (O(n) in the worst case).
Difference from DFS: DFS goes deep along a branch (pre/in/postorder), while level-order is BFS across levels.
Applications: printing/serializing trees, "right/left view" problems, connecting next pointers between siblings, per-level sums, finding the shortest path in unweighted structures, and so on.

Example tree and expected result

Tree:

    1
   / \
  2   3
 / \   \
4   5   6

Levels: [[1], [2, 3], [4, 5, 6]]
Flat: [1, 2, 3, 4, 5, 6]

Iterative implementation (JavaScript, binary tree)

// Node definition for context:
// function TreeNode(val, left=null, right=null) { this.val = val; this.left = left; this.right = right; }

function levelOrder(root) {
  if (!root) return [];
  const res = [];
  const q = [root]; // queue
  let head = 0;     // pointer to the queue's "head" (avoids O(n) shift)

  while (head < q.length) {
    const size = q.length - head; // number of nodes at the current level
    const level = [];

    for (let i = 0; i < size; i++) {
      const node = q[head++];
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }

    res.push(level);
  }
  return res;
}

// Example:
// const root = new TreeNode(1,
//   new TreeNode(2, new TreeNode(4), new TreeNode(5)),
//   new TreeNode(3, null, new TreeNode(6))
// );
// console.log(levelOrder(root)); // [[1], [2, 3], [4, 5, 6]]

N-ary tree (JavaScript)

// N-ary tree node: { val, children: Node[] }
function levelOrderN(root) {
  if (!root) return [];
  const res = [];
  const q = [root];
  let head = 0;

  while (head < q.length) {
    const size = q.length - head;
    const level = [];

    for (let i = 0; i < size; i++) {
      const node = q[head++];
      level.push(node.val);
      if (node.children) {
        for (const child of node.children) {
          if (child) q.push(child);
        }
      }
    }

    res.push(level);
  }
  return res;
}

Variant: flat traversal without grouping by level

function bfsFlat(root) {
  if (!root) return [];
  const out = [];
  const q = [root];
  let head = 0;
  while (head < q.length) {
    const node = q[head++];
    out.push(node.val);
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return out;
}

BFS-by-levels template (step by step)

Initialize the queue with the root; the result starts empty.
While the queue isn't empty: record size = the current level's size.
Repeat size times: dequeue a node, record its value, add all of its children to the queue.
Save the collected array as one level of the result.

Common errors and pitfalls

Using Array.shift() in JS causes O(n) dequeues; a head index is better.
Forgetting to separate levels: you need either a size variable or a level marker (a null delimiter).
Not handling an empty root: return an empty result immediately.
Confusing it with DFS and expecting a different traversal order.

Zigzag level order printing: reverse the order on even levels.
Bottom-up order: collect the levels and reverse the array of levels at the end.
Right/left side view: take the last/first element of each level.
Per-level sums/averages: accumulate aggregates while traversing.
Connecting sibling next pointers in a perfect binary tree.
Serializing/deserializing trees (for example, via a list of levels).

Comparison with preorder/inorder/postorder

Preorder (root-left-right): 1,2,4,5,3,6, a depth-first traversal, uses a stack.
Inorder (left-root-right): 4,2,5,1,3,6, applies to binary trees.
Postorder (left-right-root): 4,5,2,6,3,1, a depth-first traversal.
Level-order: 1,2,3,4,5,6 or by levels [[1],[2,3],[4,5,6]], a breadth-first traversal with a queue.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.