Skip to main content

12. Binary Tree Level Order Traversal

mediumAsked at Baidu

Return the values of a binary tree visited level by level, left to right.

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 as a list of lists, one list per level from top to bottom.

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 level tag

Recursively visit nodes carrying a depth integer; append into the depth-indexed bucket.

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

Tradeoff:

2. BFS with level slice

Use a queue; on each iteration drain exactly the count of nodes currently in the queue — that drain is one level.

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

Tradeoff:

Baidu-specific tips

Baidu drives BFS through their crawler frontier exactly like this — by-level URL fanout with per-level rate caps — so the level-slice idiom is what they grade on, not raw DFS.

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

Practice these live with InterviewChamp.AI →