Skip to main content

21. Binary Tree Level Order Traversal

mediumAsked at Freshworks

BFS a binary tree level-by-level — Freshworks uses this as the warm-up before any multi-tenant org-tree question.

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

Problem

Given the root of a binary tree, return the level order traversal of its node values — i.e., from left to right, level by level.

Constraints

  • 0 <= number of nodes <= 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. Brute force (DFS with depth)

DFS while tracking depth and pushing into result[depth]. Works but obscures the BFS shape the interviewer wants.

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

Tradeoff:

2. BFS with queue, batch per level

Use a queue. Each iteration of the outer loop snapshots the current queue length as the level's size, then drains exactly that many nodes pushing their values and enqueueing their children.

Time
O(n)
Space
O(n)
function levelOrder(root) {
  if (!root) return [];
  const out = [], q = [root];
  while (q.length) {
    const size = q.length, level = [];
    for (let i = 0; i < size; i++) {
      const node = q.shift();
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    out.push(level);
  }
  return out;
}

Tradeoff:

Freshworks-specific tips

Freshworks specifically wants the BFS form because their follow-up is 'now do zigzag' (LC #103) — having the queue + size-snapshot scaffold makes the follow-up trivial.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →