Binary Tree Level Order Traversal DSA Solution

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.

Input	Output	Why
`[3,9,20,null,null,15,7]`	`[[3],[9,20],[15,7]]`	Nodes are grouped by distance from the root.

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

Queue at level start	Level collected	Children added
`[3]`	`[3]`	`9, 20`
`[9,20]`	`[9,20]`	`15, 7`
`[15,7]`	`[15,7]`	none

Complexity

Measure	Value	Reason
Time	O(n)	Each node is enqueued and dequeued once.
Space	O(w)	The queue stores up to the maximum tree width.

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

Why use BFS instead of DFS?

BFS naturally visits nodes level by level, which matches the output format.

Why store the queue size?

It separates the current level from children added for the next level.

What is the core pattern?

BFS with a queue.

Binary Tree Level Order Traversal: BFS queue Pattern