LeetCode · #102

Binary Tree Level Order Traversal Solution

Given the root of a binary tree, return the level order traversal — values grouped by level, left to right.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #102

🏗️

Pattern

BFS — queue with level grouping

Given the root of a binary tree, return its level order traversal as a list of lists — each inner list contains the values of nodes at that depth level, from left to right.

Example

 Input: 3
        / \
       9   20
          /  \
         15   7
Output: [[3], [9, 20], [15, 7]]

Constraints

• 0 ≤ number of nodes ≤ 2000 • -1000 ≤ Node.val ≤ 1000

Section Two · Approach 1

DFS with Depth Tracking — O(n)

DFS (preorder), passing the current depth. Use a list of lists where depth is the index. Append values at their depth. Works but doesn't process nodes in a natural level-by-level order.

Section Three · Approach 2

BFS with Queue — O(n)

Use a queue. At each level, process all nodes currently in the queue (that's one level), collect their values, and enqueue their children. The queue naturally separates levels.

💡 Mental model: Imagine a stadium where each row is a level. You photograph row 1 (just the root), then row 2 (root's children), then row 3, etc. At each row, you snap all people in that row before moving to the next. The queue holds the current row.

Algorithm

Step 1: If root is null, return empty list.
Step 2: Initialize queue with root.
Step 3: While queue not empty:
levelSize = queue.size() — snapshot current level count.
Process exactly levelSize nodes: dequeue, collect value, enqueue children.
Add collected values as a new level to result.

🎯 Key trick — levelSize snapshot:

Before processing, capture queue.size(). This is how many nodes belong to the current level.
New children enqueued during this loop belong to the next level and won't be processed until the next iteration.

Section Four · Trace

Visual Walkthrough

BFS level-by-level — queue snapshot per level

Section Five · Implementation

Code — Java & Python

Java — BFS with Queue

 import java.util.*;
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
                level.add(node.val);
if (node.left != null)  queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
            }

            result.add(level);
        }
return result;
    }
}

Python — BFS with deque

 from collections import deque
class Solution:
def levelOrder(self, root):
if not root: return []

        result = []
        queue = deque([root])
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)
            result.append(level)
return result

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
BFS Queue	O(n)	O(n) — queue holds widest level
DFS + depth index	O(n)	O(h) stack + O(n) result

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty	`null`	Return []. Check before enqueuing.
Single node	`[1]`	Result: [[1]]. One level.
Skewed left	`1→2→3`	Result: [[1],[2],[3]]. One node per level.
Complete tree	Full binary tree	Widest level has n/2 nodes → queue peaks at O(n).

⚠ Common Mistake: Not capturing queue.size() before the for-loop. If you use queue.size() directly in the loop condition, it changes as you add children — mixing levels in the same list.

← Back to Trees problems

LearningTree

LC 102 · Binary Tree Level Order Traversal — Solution & Explanation | DSA Guide