Binary Tree Level-Order Traversal — BFS, Zigzag, and Right Side View

Most tree problems run on DFS — you go deep, hit a base case, return something. Level-order traversal is the exception. You can't do it with a simple recursive DFS because you need to process all nodes at depth 1 before any nodes at depth 2, and recursion interleaves them. You need a queue.

This is the BFS (breadth-first search) pattern for trees. Once you have it, three problems that look like they require completely different algorithms turn out to be the same loop with a small variation each time.

The Core BFS Template

Here's the skeleton every tree BFS problem fits:

const bfs = (root) => {
  if (!root) return [];
  const result = [];
  let queue = [root];
 
  while (queue.length) {
    const levelSize = queue.length;  // snapshot: nodes at this level
    const level = [];
    const next = [];                 // children land here, not behind a shift()
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[i];         // read by index — see the note below
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
 
    result.push(level);
    queue = next;                    // the next frontier becomes the queue
  }
  return result;
};

The key insight: at the start of each while-loop iteration, everything currently in the queue is at the same depth. queue.length at that moment is the level size. Process exactly that many nodes, collect their children, and you've finished one level. The children become the queue for the next iteration.

Visualizing BFS on a Binary Tree

Each level is processed as a batch. The queue holds exactly the next frontier at any point.

Problem 1: Binary Tree Level Order Traversal (LC 102)

Return all node values grouped by level: [[3], [9, 20], [15, 7]] for the tree above.

Brute Force: DFS with Depth Tracking

You can do this with DFS by threading the current depth as a parameter and indexing into the result array.

// Input: root = [3,9,20,null,null,15,7]
// Output: [[3],[9,20],[15,7]]
 
const levelOrderDFS = (root) => {
  const result = [];
 
  const dfs = (node, depth) => {
    if (!node) return;
    if (result.length === depth) result.push([]);  // new level
    result[depth].push(node.val);
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  };
 
  dfs(root, 0);
  return result;
};
// Time: O(n) | Space: O(h) — call stack depth h (worst case O(n) for skewed tree)

This works, but it doesn't feel like BFS — you lose the natural "process one level at a time" structure. The solution also has O(h) call stack overhead where h is the tree height.

Optimized: Iterative BFS with Queue

// Input: root = [3,9,20,null,null,15,7]
// Output: [[3],[9,20],[15,7]]
 
const levelOrder = (root) => {
  if (!root) return [];
 
  const result = [];
  let queue = [root];
 
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    const next = [];
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[i];
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
 
    result.push(level);
    queue = next;
  }
 
  return result;
};
// Time: O(n) — every node is read once, and reading by index is O(1)
// Space: O(w) — two adjacent levels at most (worst case O(n) for complete trees)

The BFS version is cleaner for level-grouping problems because the level boundary is naturally encoded by queue.length at the start of each iteration.

Problem 2: Zigzag Level Order Traversal (LC 103)

Same as level-order, but alternate the direction each level: left-to-right at even depths, right-to-left at odd depths.

Level 0 (L→R): [3]
Level 1 (R→L): [20, 9]
Level 2 (L→R): [15, 7]

Brute Force: BFS then Reverse

Do standard level-order, then reverse every other level's array.

// Input: root = [3,9,20,null,null,15,7]
// Output: [[3],[20,9],[15,7]]
 
const zigzagLevelOrderBrute = (root) => {
  if (!root) return [];
 
  const result = [];
  let queue = [root];
  let leftToRight = true;
 
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    const next = [];
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[i];
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
 
    result.push(leftToRight ? level : [...level].reverse());
    leftToRight = !leftToRight;
    queue = next;
  }
 
  return result;
};
// Time: O(n) — extra O(w) per level for reverse, amortized O(n) total
// Space: O(w) — queue width

The reversal is O(width of that level) per level, O(n) total. This is acceptable.

Optimized: Fill Array by Direction

Instead of building then reversing, fill into a fixed-size array from the correct end.

// Input: root = [3,9,20,null,null,15,7]
// Output: [[3],[20,9],[15,7]]
 
const zigzagLevelOrder = (root) => {
  if (!root) return [];
 
  const result = [];
  let queue = [root];
  let leftToRight = true;
 
  while (queue.length) {
    const levelSize = queue.length;
    const level = new Array(levelSize);
    const next = [];
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[i];
      // Write to front or back depending on direction
      const idx = leftToRight ? i : levelSize - 1 - i;
      level[idx] = node.val;
 
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
 
    result.push(level);
    leftToRight = !leftToRight;
    queue = next;
  }
 
  return result;
};
// Time: O(n) | Space: O(w) — no post-processing reversal step

Problem 3: Binary Tree Right Side View (LC 199)

Imagine standing to the right of the tree. Return the values you can see — one per level, whichever node is rightmost.

    3         ← you see 3
   / \
  9  20       ← you see 20
    /  \
   15   7     ← you see 7
Output: [3, 20, 7]

Brute Force: Full Level-Order, Take Last

Do standard level-order, collect every level, then grab the last element of each.

// Input: root = [3,9,20,null,null,15,7]
// Output: [3,20,7]
 
const rightSideViewBrute = (root) => {
  if (!root) return [];
 
  const result = [];
  let queue = [root];
 
  while (queue.length) {
    const levelSize = queue.length;
    const next = [];
    let lastVal;
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[i];
      lastVal = node.val;  // overwrite until the last node this level
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
 
    result.push(lastVal);
    queue = next;
  }
 
  return result;
};
// Time: O(n) | Space: O(w)

This is already efficient — O(n) time and O(w) space where w is the max width. The "optimized" version below is just a stylistic variant.

Optimized: Right-Child-First BFS

Enqueue right before left, then the first node dequeued each level is always the rightmost.

// Input: root = [3,9,20,null,null,15,7]
// Output: [3,20,7]
 
const rightSideView = (root) => {
  if (!root) return [];
 
  const result = [];
  let queue = [root];
 
  while (queue.length) {
    const levelSize = queue.length;
    const next = [];
    result.push(queue[0].val);  // First node in queue = rightmost at this level
 
    for (let i = 0; i < levelSize; i++) {
      const node = queue[i];
      // Collect right first so right children lead next level
      if (node.right) next.push(node.right);
      if (node.left) next.push(node.left);
    }
 
    queue = next;
  }
 
  return result;
};
// Time: O(n) | Space: O(w)

The BFS Template Unification

All three problems use the same skeleton:

while queue not empty:
  levelSize = queue.length      ← level boundary
  for i in range(levelSize):
    node = dequeue
    [do something with node.val]
    enqueue node.left, node.right
  [do something with the collected level]

What changes between problems:

• LC 102: push level array as-is
• LC 103: push level reversed on odd depths
• LC 199: push only level[last] or level[0]

When you see a new tree BFS problem, fit it into this template first.

Interview Tips

The levelSize snapshot is the key move. Interviewers sometimes see candidates who forget to capture queue.length at the start of each iteration — they query it inside the loop, and it keeps growing as children are added. This is the most common BFS bug. Capture it once at the top of the while-loop.

BFS vs DFS on trees: BFS uses O(w) space (width of the tree), DFS uses O(h) space (height). For a balanced tree, height is O(log n) and width can be O(n/2) at the bottom level — so DFS is more memory efficient. For a completely unbalanced (linear) tree, DFS is O(n) space (call stack) and BFS is O(1). In interviews, BFS is preferred when the problem explicitly involves levels, shortest paths, or "nearest" anything.

On right side view: A common variant is "left side view" — same problem, take the first node per level instead of the last, or enqueue left before right. If an interviewer asks this as a follow-up, you can answer in one sentence: "Same BFS, just grab queue[0] before the level loop instead of the last value after."

Know when BFS applies: It's the right instinct for "shortest path," "minimum depth," "level by level," and "closest node." If the problem doesn't involve levels or distances, DFS is usually simpler.

Using two arrays instead of shift: Every listing above already does this — read the current level by index, collect children into a next array, then queue = next. It avoids the O(queue length) shift, keeps the queue at O(w), and is why the O(n) annotations are literally true rather than "true if you assume an O(1) dequeue." For interviews queue.shift() is accepted and expected; mention you know it re-indexes the array and that you'd swap in two arrays (or an index cursor) in production code, then move on — don't get bogged down optimizing array operations unless asked.