Skip to main content

62. Binary Tree Level Order Traversal

mediumAsked at Datadog

Return a binary tree's level-order traversal grouped by level. Datadog uses this as the BFS-foundation question — same level-batched pattern they use for paginated tree expansion in their query layer.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite BFS warmup.
  • Blind (2025-12)— Recurring Datadog 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. DFS tracking depth

Recurse; pass depth; append node.val to out[depth].

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

Tradeoff: Works but not the BFS pattern Datadog expects. Use this only if iterative BFS is forbidden.

2. BFS with level batches (optimal)

Queue. At each iteration, process ALL nodes at the current level (q.length captures the level size), then move to next.

Time
O(n)
Space
O(w)
function levelOrder(root) {
  if (!root) return [];
  const out = [];
  let q = [root];
  while (q.length) {
    const level = [];
    const next = [];
    for (const n of q) {
      level.push(n.val);
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    out.push(level);
    q = next;
  }
  return out;
}

Tradeoff: Single pass. The level-batch BFS pattern is the Datadog-canonical iteration over hierarchical structures.

Datadog-specific tips

Datadog will follow up with: 'Return only the rightmost node per level' (right-side view) or 'Zigzag the levels.' Show that BOTH are tiny variants of the level-batch BFS — change which value you push, or reverse alternate levels.

Common mistakes

  • Using a single queue without capturing level size — mixes nodes from different levels.
  • Pushing left/right unconditionally even when null — wastes time on null processing.
  • Allocating one queue per level and copying — slower than building 'next' array.

Follow-up questions

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

  • Binary Tree Right Side View (LC 199) — emit only the last per level.
  • Binary Tree Zigzag Level Order (LC 103) — alternate direction.
  • Datadog-style: paginated tree expansion in a hierarchical metric explorer.

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 two arrays (q and next)?

Cleaner than mutating q in place. The level-size trick (saving q.length before the loop) achieves the same with one queue but is harder to read.

BFS or DFS?

Both work. BFS is more natural for level-batched output. DFS via depth-passing is also accepted.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →