Binary Tree Level Order Traversal: BFS queue Pattern

Learning Outcome

After this lesson, you should be able to use a queue to group binary tree nodes level by level.

Problem Statement

Given the root of a binary tree, return the level order traversal of its node values. Each level should be grouped in its own list.

Brute Force Approach

Run DFS separately for each depth and collect nodes at that depth.

This can revisit nodes many times. BFS gives each level directly in one traversal.

Optimized Approach

Use a queue. At the start of each level, record the current queue size. Pop exactly that many nodes to build one level, then push their children for the next level.

Exact Pseudocode

if root is null:
  return []
queue = [root]
answer = []
while queue is not empty:
  size = queue.length
  level = []
  repeat size times:
    node = queue.pop_front()
    level.add(node.val)
    if node.left exists: queue.push_back(node.left)
    if node.right exists: queue.push_back(node.right)
  answer.add(level)
return answer
  

Reference Code

from collections import deque

class Solution:
    def levelOrder(self, root):
        if not root:
            return []

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

        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            answer.append(level)

        return answer
  

Sample Dry Run

Complexity

Edge Cases

• Empty tree returns an empty list.
• Single-node tree returns one level.
• Do not let newly added children affect the current level's loop count.

Interview Checklist

• Snapshot queue size before processing a level.
• Pop exactly that many nodes.
• Add children for the next level only.

FAQs