MediumBreadth-First SearchTreeUpdated Sep 2026

102. Binary Tree Level Order Traversal

Asked at Google, Meta, Amazon, Microsoft and 4 more

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Breadth-First Search

Companies

8

Problem

You are given the root of a binary tree. Return the values of all nodes grouped by level, from the top level down to the bottom, and from left to right inside each level.

The answer is a list of lists. The first inner list holds the root's value, the second holds the values on the next level, and so on. If the tree is empty, return an empty list.

This is a breadth-first search (BFS) problem: you visit all nodes at one depth before touching any node at a deeper depth.

Group values by depth

9level 13level 015level 2207Level 0 = [3], level 1 = [9,20], level 2 = [15,7]
The tree has three levels, so the answer has three inner lists, each read left to right.

Constraints

  • ●The number of nodes in the tree is in the range [0, 2000].
  • ●-1000 <= Node.val <= 1000

Examples

Example 1
Inputroot = [3,9,20,null,null,15,7]
Output[[3],[9,20],[15,7]]
WhyLevel 0 has only the root, 3. Level 1 has its two children, 9 and 20, read left to right. Level 2 has the children of 20, which are 15 and 7.
Example 2
Inputroot = [1]
Output[[1]]
WhyThe tree is a single node, so there is just one level with one value.
Example 3
Inputroot = []
Output[]
WhyThere are no nodes, so there are no levels to report.

Asked At

8 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
NetflixMediumView all Netflix questions →
UberMediumView all Uber questions →
AtlassianMediumView all Atlassian questions →

How to Think About It

1

Use a queue for BFS. Enqueue the root. Process all nodes at the current level before moving to the next.

2

The key trick: record the queue size at the start of each level. Process exactly that many nodes. This separates levels.

3

For each node processed: dequeue it, add its value to the current level list, enqueue its children (left then right).

4

This pattern extends to many tree problems: right side view (take last node per level), zigzag (alternate left/right), maximum width (count nodes per level).

Optimal Approach

Step 1: If root is null, return [].
Step 2: Initialize queue with root.
Step 3: While queue not empty:
- Record queue size (= nodes at current level)

  • Process that many nodes:
  • Dequeue node
  • Add value to current level list
  • Enqueue left child (if exists)
  • Enqueue right child (if exists)
  • Add level list to result
    Step 4: Return result.

The for-loop over range(len(q)) at each level is critical. It processes exactly the nodes at the current level, not any newly added children.

Time: O(n). Space: O(n) for the queue.

BFS with a queue

queue3frontbackStart: only the root is in the queue. Size = 1, sothis level has 1 node.queue920frontbackPop 3, record it, push 9 then 20. Size = 2, so thislevel has 2 nodes.queue157frontbackPop 9 (no children), pop 20 and push 15 then 7. Size =2 again.for _ in range(len(q)): node = q.popleft() level.append(node.val) push left, then right
At each level we freeze the queue size, pop exactly that many nodes, and push their children for the next round.
ComplexityTime O(n)Space O(n)Every node enters and leaves the queue once; the queue can hold up to one full level, which is O(n) in the worst case.

What Trips People Up in Real Interviews

1

Confusing BFS with DFS. Level order traversal is BFS — use a queue. DFS (preorder/inorder/postorder) doesn't give you level-by-level grouping naturally.

2

Not processing all nodes at the current level before moving to the next. Use a for loop over the current queue size to separate levels.

3

Forgetting to handle null children. When adding children to the queue, only add non-null children.

4

Not handling an empty tree. Return an empty list, not null.

5

Using a stack instead of a queue. A stack gives you DFS (preorder), not BFS. Level order traversal requires a queue for FIFO processing to visit nodes level by level.

Solution Code

O(n) time
from collections import deque

def levelOrder(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Binary Tree Level Order Traversal 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). This is the most common tree BFS problem in FAANG interviews.

How do you solve Binary Tree Level Order Traversal?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Binary Tree Level Order Traversal?

Binary Tree Level Order Traversal is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian. It is a medium difficulty problem.

What are common mistakes on Binary Tree Level Order Traversal?
  • Confusing BFS with DFS. Level order traversal is BFS — use a queue. DFS (preorder/inorder/postorder) doesn't give you level-by-level grouping naturally.
  • Not processing all nodes at the current level before moving to the next. Use a for loop over the current queue size to separate levels.
  • Forgetting to handle `null` children. When adding children to the queue, only add non-`null` children.
  • Not handling an empty tree. Return an empty list, not `null`.
  • Using a stack instead of a queue. A stack gives you DFS (preorder), not BFS. Level order traversal requires a queue for FIFO processing to visit nodes level by level.