Skip to main content

70. Binary Tree Level Order Traversal

mediumAsked at Plaid

Return the level-order traversal of a binary tree's values. Plaid asks this as a BFS baseline before harder graph-walks on payment-rail dependency trees.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA — BFS classic.
  • Blind (2026)— Plaid backend onsite.

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 = []
Output
[]

Approaches

1. DFS with level index

DFS preorder; for each node, append to out[depth].

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

Tradeoff: Works but uses recursion stack. Less natural for level-order than BFS.

2. BFS with level batching

Queue. Each outer iteration processes one full level: snapshot the queue size, drain that many.

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

Tradeoff: Two-array approach avoids the size-snapshot trick. Clean iteration: process current level, build next.

Plaid-specific tips

Plaid prefers BFS for level-order because it's the natural framing. Bonus signal: discuss when DFS-with-depth is cleaner (when you only need a per-depth aggregate, not the full grouping). Connect to payment-rail dependency tree where each level represents a hop and we need to process all hops at depth d before depth d+1.

Common mistakes

  • Using a single queue without level boundaries — outputs a flat list.
  • Using shift() on an array — O(n) per call.
  • Forgetting the empty-root early return.

Follow-up questions

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

  • Reverse level order (LC 107).
  • Zigzag level order (LC 103).
  • Right-side view of a tree (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

BFS or DFS?

BFS is the natural fit for level-order. DFS works with a depth parameter but feels backward — you're recording level info as you descend, not as you traverse the level.

Why two-array over single queue?

Two arrays make the level boundary explicit. Single queue + size snapshot also works but has more state to track.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →