Skip to main content

102. Binary Tree Level Order Traversal

mediumAsked at Cisco

Binary Tree Level Order Traversal at Cisco is the canonical BFS-on-tree problem. The interviewer is checking whether you snapshot the queue size at the start of each level loop — the trick that turns a flat BFS into a grouped-by-level output.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-II onsite reports list level-order traversal as a 30-minute coding round.
  • Blind (2025-11)— Cisco interview thread cites this as a recurring tree question.

Problem

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Constraints

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
[[3],[9,20],[15,7]]

Example 2

Input
root = [1]
Output
[[1]]

Example 3

Input
root = []
Output
[]

Approaches

1. Brute-force: depth-tagged DFS, group by depth

Run a DFS that carries depth. Push each value into result[depth]. Result is grouped by level.

Time
O(n)
Space
O(n)
function levelOrderDFS(root) {
  const result = [];
  function dfs(node, depth) {
    if (!node) return;
    if (!result[depth]) result[depth] = [];
    result[depth].push(node.val);
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  }
  dfs(root, 0);
  return result;
}

Tradeoff: Correct, same Big-O. Less idiomatic for 'level order' because DFS doesn't naturally enforce level-by-level. Bring this up as the alternative and pivot to BFS as the canonical answer.

2. BFS with level-size snapshot (optimal)

Standard BFS with a queue, but at the start of each iteration capture `queue.length` so you process exactly one level at a time.

Time
O(n)
Space
O(n)
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    const levelSize = queue.length;
    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;
}

Tradeoff: The `levelSize` snapshot is what separates this from a flat BFS. Without it, you'd dequeue children from later levels mid-loop and lose the grouping. This is the idiomatic answer.

Cisco-specific tips

Cisco interviewers grade this on whether you snapshot queue.length BEFORE the inner loop. State out loud: 'I capture levelSize because by the end of this inner loop the queue will hold the NEXT level — I need the SIZE of the current level frozen.' That single sentence earns full marks. They also like you handling the empty-root case as the first line.

Common mistakes

  • Not snapshotting `queue.length` — you process current AND next level in the same loop iteration and lose the grouping.
  • Forgetting to check `if (node.left)` / `if (node.right)` and pushing nulls onto the queue — the next dequeue then null-dereferences.
  • Using `queue.shift()` in JS (O(n)) on very large trees — note this to the interviewer and offer to swap in a proper deque.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

  • Zigzag Level Order (LC 103) — reverse alternating levels.
  • Right Side View (LC 199) — last node of each level.
  • Average of Levels (LC 637) — same scaffold, different aggregate.
  • Vertical Order Traversal (LC 314 — Meta favorite). Different traversal but similar BFS scaffold.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why BFS over DFS here?

Both work, but the problem is LITERALLY phrased as 'level order' so BFS is the idiomatic match. DFS tagged-with-depth produces the same output but is less natural to explain — the interviewer expects 'queue + level snapshot' as the first instinct.

What's the queue.shift() performance concern?

JS array.shift() is O(n) because it slides every other element down by one. On the LeetCode constraint upper bound (2000 nodes) it's fine, but in production code at Cisco scale you'd use a circular buffer or two-stack deque to keep BFS at O(n) total.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Binary Tree Level Order Traversal and other Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →