Skip to main content

74. Binary Tree Level Order Traversal

mediumAsked at Ola

Return the level-order traversal of a binary tree.

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

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

  • Number of nodes is in [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 depth indexing

Recurse and append values into the bucket for the depth.

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

Tradeoff:

2. BFS with size snapshot

Maintain a queue; for each level snapshot current size and pop exactly that many.

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

Tradeoff:

Ola-specific tips

Ola favors the size-snapshot BFS pattern; tie it to producing per-hop driver buckets when broadcasting an alert through a routing tree.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →