Problem

Given the root of a binary tree, return the level order traversal of the tree.

Instead of returning all values in one list, we return a list of lists, where each inner list contains the nodes at the same depth, from left to right.

Example

Input:
        1
      /   \
     2     3
    / \   / \
   4  5  6   7

Output:
[[1], [2,3], [4,5,6,7]]

Intuition

This problem is one of the most classic applications of Breadth-First Search (BFS).

Unlike DFS, which explores one branch as deeply as possible, BFS explores the tree level by level.

The idea is simple:

  • Start with the root.
  • Process every node currently in the queue (this represents one level).
  • While processing those nodes, add their children to the queue.
  • Once we've processed every node at the current level, we've completed one row of our answer.

The key observation is:

At the start of each iteration, the queue contains exactly one level of the tree.

Algorithm

  1. Handle the empty tree.
  2. Create a queue and place the root inside.
  3. While the queue isn't empty:
    • Record the current queue size (this is the number of nodes on the current level).
    • Create an empty list for this level.
    • Process exactly that many nodes:
      • Remove a node from the queue.
      • Add its value to the current level.
      • Push its left child (if it exists).
      • Push its right child (if it exists).
    • Append the completed level to the answer.
  4. Return the result.

Solution

from typing import List, Optional
from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        res = []
        queue = deque([root])

        while queue:
            subList = []

            for _ in range(len(queue)):
                node = queue.popleft()
                subList.append(node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            res.append(subList)

        return res

Walkthrough

Consider this tree:

        1
      /   \
     2     3
    / \   / \
   4  5  6   7

Initial queue

[1]

Level 1

Queue size = 1

Process node 1

Current level = [1]

Queue becomes:
[2,3]

Result:

[[1]]

Level 2

Queue size = 2

Process 2

Current level = [2]

Queue:
[3,4,5]

Process 3

Current level = [2,3]

Queue:
[4,5,6,7]

Result:

[[1],[2,3]]

Level 3

Queue size = 4

Process:

4
5
6
7

Current level:

[4,5,6,7]

Queue becomes empty.

Final result:

[[1],[2,3],[4,5,6,7]]

Why len(queue) Is Important

Many beginners wonder why we write:

for _ in range(len(queue)):

instead of simply:

while queue:

The reason is that we're adding children to the queue while processing the current level.

For example:

Queue:
[2,3]

If we simply processed until the queue became empty, we'd immediately continue with nodes 4, 5, 6, and 7, mixing multiple levels together.

Instead, we first record:

level_size = len(queue)

which tells us exactly how many nodes belong to the current level.

Any children added during the loop are processed in the next iteration of the outer while loop.

Complexity Analysis

Let n be the number of nodes.

Time Complexity

Each node is:

  • Added to the queue once
  • Removed from the queue once

Therefore:

Time: O(n)

Space Complexity

In the worst case, the queue may contain an entire level of the tree.

For a balanced tree, the last level contains roughly n/2 nodes.

Space: O(n)

Why BFS?

This problem naturally asks us to visit nodes level by level, making BFS the ideal traversal.

While DFS can also solve the problem by keeping track of each node's depth, BFS is:

  • More intuitive
  • Simpler to implement
  • The approach most interviewers expect for level-order traversal problems

If you see phrases like:

  • "level order"
  • "level by level"
  • "nodes at each depth"

it's a strong signal that Breadth-First Search using a queue is the right tool.

Key Takeaways

  • Use BFS whenever you need to process a tree one level at a time.
  • The queue always stores the nodes waiting to be processed.
  • len(queue) tells us exactly how many nodes belong to the current level.
  • Children are added to the queue for processing in the next iteration.
  • This solution runs in O(n) time with O(n) auxiliary space and is the standard interview solution for this problem.