21. Binary Tree Level Order Traversal

Q: Why snapshot the queue length instead of using a null sentinel?

Snapshotting the queue length at the start of each while-loop iteration is cleaner and avoids managing null nodes in the queue, which can cause null-pointer issues. The snapshot precisely captures how many nodes belong to the current level.

Q: How do I do this for a general tree (n-ary)?

Replace node.left and node.right with a loop over node.children. The level-size snapshot technique works identically for any branching factor.

mediumAsked at ServiceNow

Return all node values of a binary tree grouped by level, using BFS. ServiceNow asks this because hierarchical BFS represents approval tiers in their workflow engine — each level is a stage gate — and the level-grouping technique surfaces directly in their reporting dashboards.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

LeetCode Discuss (2025)— Cited as a ServiceNow SDE-I onsite warm-up for BFS tree traversal.
Glassdoor (2026)— Reported in ServiceNow new-grad and mid-level loops.

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). The result is a list of lists, where each inner list contains the node values at that depth.

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]]

Explanation: Level 0: [3], level 1: [9, 20], level 2: [15, 7].

Example 2

Input

root = [1]

Output

[[1]]

Approaches

1. DFS with depth tracking

Recursive DFS; pass depth as an argument and append node.val to result[depth].

Time: O(n)
Space: O(n)

function levelOrder(root) {
  const result = [];
  function dfs(node, depth) {
    if (!node) return;
    if (result.length === depth) result.push([]);
    result[depth].push(node.val);
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  }
  dfs(root, 0);
  return result;
}

Tradeoff: Correct, but DFS processes nodes left-to-right-within-level only by convention — BFS is the canonical approach and more directly expresses level-by-level intent.

2. Iterative BFS with level-size snapshot

Use a queue initialized with root. At the start of each iteration, snapshot the current queue length — that is the number of nodes in the current level. Process exactly that many nodes, collecting their values into a level array, then enqueue children.

Time: O(n)
Space: O(n)

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

  while (queue.length > 0) {
    const levelSize = queue.length; // snapshot
    const levelVals = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      levelVals.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(levelVals);
  }
  return result;
}

Tradeoff: The level-size snapshot is the key technique. Replacing queue.shift() with an index pointer improves performance from O(n^2) to O(n) on the shift operation.

ServiceNow-specific tips

ServiceNow interviewers specifically ask 'how do you know when one level ends and the next begins?' — the level-size snapshot answer is what they want. Candidates who use a sentinel null node to delimit levels are penalized for unclean design. Bonus signal: describe how each level in the output maps directly to a ServiceNow approval tier, making it easy to show which approvers are at each stage.

Common mistakes

Using queue.shift() in a tight loop without caching the initial queue length — processes nodes from the next level in the same iteration, mixing levels.
Not handling the empty tree (root === null) — returns [[]] instead of [].
Appending the node.val before snapshotting levelSize — shifts the boundary by one if you use a pre-increment strategy.

Follow-up questions

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

Level order traversal II: return levels in bottom-up order (LC 107).
Zigzag level order traversal: alternate left-to-right and right-to-left (LC 103).
Right side view: return the last node at each level (LC 199).

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 snapshot the queue length instead of using a null sentinel?

Snapshotting the queue length at the start of each while-loop iteration is cleaner and avoids managing null nodes in the queue, which can cause null-pointer issues. The snapshot precisely captures how many nodes belong to the current level.

How do I do this for a general tree (n-ary)?

Replace node.left and node.right with a loop over node.children. The level-size snapshot technique works identically for any branching factor.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →