Skip to main content

17. Binary Tree Level Order Traversal

mediumAsked at Nubank

Return a binary tree's node values level by level; Nubank uses BFS-with-level-snapshots to test queue discipline before deeper org-hierarchy / category-tree questions.

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 as a list of lists — each inner list contains all values at one depth, from top down, left to right.

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 tagging

Recurse with a depth parameter; push values into the row indexed by depth.

Time
O(n)
Space
O(n)
function levelOrder(root){ 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-size snapshot

Push the root, then in each outer loop drain exactly the current queue size into one row before the next level enters.

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

Tradeoff:

Nubank-specific tips

Nubank loves the iterative BFS — recruiters say it's an analog for breadth-first sweeps over MCC category trees during merchant-categorization.

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

Practice these live with InterviewChamp.AI →