Skip to content

140. Binary Tree Level Order Traversal

🔗 LeetCode Problem: 102. Binary Tree Level Order Traversal
📊 Difficulty: Medium
🏷️ Topics: Binary Trees, BFS, Queue, Level Order, DFS

Problem Statement

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).

Example 1: 

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2: 

Input: root = [1]
Output: [[1]]

Example 3: 

Input: root = []
Output: []

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

🌳 Visual Understanding - Level by Level!

What is Level Order Traversal?

Level Order = Visit nodes LEVEL BY LEVEL
Also called: Breadth-First Search (BFS)

Tree:
       3           ← Level 0
      / \
     9   20       ← Level 1
        /  \
       15   7     ← Level 2

Level 0: [3]
Level 1: [9, 20]
Level 2: [15, 7]

Result: [[3], [9, 20], [15, 7]]

Pattern: Horizontal layers, left to right!

Example 1: Complete Visual

Tree:
              3                    ← Level 0: [3]
            /   \
           9     20                ← Level 1: [9, 20]
                /  \
               15   7              ← Level 2: [15, 7]

Processing order:
  Step 1: Visit level 0 → [3]
  Step 2: Visit level 1 → [9, 20]
  Step 3: Visit level 2 → [15, 7]

Output: [[3], [9, 20], [15, 7]]

Each level is a separate list!

Example 2: Unbalanced Tree

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

Level 0: [1]
Level 1: [2, 3]
Level 2: [4, 5, 6]
Level 3: [7]

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

Levels can have different sizes!

🧠 The AHA Moment - BFS vs DFS!

DFS (What We've Been Using):

DFS = Depth-First Search
Goes DEEP before WIDE

Inorder example:
       1
      / \
     2   3
    / \
   4   5

Order: 4 → 2 → 5 → 1 → 3
Pattern: Goes deep (to 4) before exploring siblings

Visual path: 1 → 2 → 4 (deep!) → back → 5 → back → back → 3

BFS (Level Order):

BFS = Breadth-First Search
Goes WIDE before DEEP

Level order:
       1
      / \
     2   3
    / \
   4   5

Order: 1 → 2 → 3 → 4 → 5
Pattern: Complete each level before going deeper

Visual path: Level 0 (1) → Level 1 (2,3) → Level 2 (4,5)

Key Difference:

DFS uses: STACK (or recursion call stack)
  - Last In, First Out (LIFO)
  - Goes deep like a stack of plates

BFS uses: QUEUE
  - First In, First Out (FIFO)
  - Goes wide like a waiting line

This is THE fundamental difference!

🧠 BFS Strategy - Using Queue

How Queue Works for BFS:

Queue = FIFO (First In, First Out)

Process:
1. Add root to queue
2. While queue not empty:
   a. Count how many nodes at current level
   b. Process all nodes at current level
   c. Add their children (next level) to queue
3. Repeat for each level

Why this works:
  - Queue naturally processes level by level
  - All nodes of level N come before level N+1
  - Perfect for BFS!

Visual Queue Operation:

Tree:
       1
      / \
     2   3

Initial:
  queue = [1]
  result = []

Process Level 0:
  levelSize = 1 (queue has 1 node)

  Process node 1:
    Remove 1 from queue
    Add 1 to currentLevel → [1]
    Add children: 2, 3 to queue

  queue = [2, 3]
  result = [[1]]

Process Level 1:
  levelSize = 2 (queue has 2 nodes)

  Process node 2:
    Remove 2 from queue
    Add 2 to currentLevel → [2]
    Add children: none

  Process node 3:
    Remove 3 from queue
    Add 3 to currentLevel → [2, 3]
    Add children: none

  queue = []
  result = [[1], [2, 3]]

Done! Queue is empty.

🎯 Solution 1: BFS with Queue (Standard Approach)

Implementation:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        // Edge case: empty tree
        if (root == null) {
            return result;
        }

        // Create queue and add root
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // Process level by level
        while (!queue.isEmpty()) {
            // Get number of nodes at current level
            // WHY? Need to process exactly this many nodes
            int levelSize = queue.size();

            // List for current level
            List<Integer> currentLevel = new ArrayList<>();

            // Process all nodes at current level
            for (int i = 0; i < levelSize; i++) {
                // Remove node from queue
                TreeNode node = queue.poll();

                // Add to current level
                currentLevel.add(node.val);

                // Add children to queue (for next level)
                // WHY? They'll be processed in next iteration
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            // Add current level to result
            result.add(currentLevel);
        }

        return result;
    }
}

The Critical Pattern:

while (!queue.isEmpty()) {
    int levelSize = queue.size();  // ← CRITICAL!

    for (int i = 0; i < levelSize; i++) {
        // Process exactly levelSize nodes
        // This ensures we process one complete level
    }
}

Without levelSize:
  - Would process nodes as they're added
  - Can't separate levels
  - Results would be mixed!

With levelSize:
  - Process exactly one level per iteration
  - Clear separation between levels
  - Perfect level-by-level processing!

🎯 Solution 2: DFS with Level Tracking (Less Common)

Can We Use DFS?

YES! But it's less intuitive.

Key idea:
  Track the LEVEL (depth) as we recurse
  Add node to the list at that level index

Example:
  recurse(node, level):
    - Add node to result[level]
    - Recurse on left with level+1
    - Recurse on right with level+1

Implementation:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        // Base case: null node
        if (node == null) {
            return;
        }

        // If this is first node at this level, create new list
        // WHY? Need a list for each level
        if (level == result.size()) {
            result.add(new ArrayList<>());
        }

        // Add current node to its level
        result.get(level).add(node.val);

        // Recurse on children with increased level
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}

Why DFS Works But Is Less Natural:

DFS order: 1 → 2 → 4 → 5 → 3 → 6

But we track levels:
  1 at level 0 → result[0] = [1]
  2 at level 1 → result[1] = [2]
  4 at level 2 → result[2] = [4]
  5 at level 2 → result[2] = [4, 5]
  3 at level 1 → result[1] = [2, 3]
  6 at level 2 → result[2] = [4, 5, 6]

Final: [[1], [2, 3], [4, 5, 6]]

Works! But order of adding is not level-by-level.
BFS is more natural for this problem.

🔍 Detailed Dry Run - BFS Approach

Tree:
       3
      / \
     9   20
        /  \
       15   7

Complete Queue Operations:

INITIAL STATE:
  queue = [3]
  result = []

═══════════════════════════════════════
ITERATION 1 - Process Level 0:
═══════════════════════════════════════

levelSize = queue.size() = 1
currentLevel = []

For loop (i = 0 to 0):
  i = 0:
    node = queue.poll() = 3
    currentLevel.add(3) → [3]

    3.left = 9, add to queue
    3.right = 20, add to queue

    queue = [9, 20]

Add currentLevel to result → [[3]]

State:
  queue = [9, 20]
  result = [[3]]

═══════════════════════════════════════
ITERATION 2 - Process Level 1:
═══════════════════════════════════════

levelSize = queue.size() = 2  ← Two nodes!
currentLevel = []

For loop (i = 0 to 1):
  i = 0:
    node = queue.poll() = 9
    currentLevel.add(9) → [9]

    9.left = null, skip
    9.right = null, skip

    queue = [20]

  i = 1:
    node = queue.poll() = 20
    currentLevel.add(20) → [9, 20]

    20.left = 15, add to queue
    20.right = 7, add to queue

    queue = [15, 7]

Add currentLevel to result → [[3], [9, 20]]

State:
  queue = [15, 7]
  result = [[3], [9, 20]]

═══════════════════════════════════════
ITERATION 3 - Process Level 2:
═══════════════════════════════════════

levelSize = queue.size() = 2
currentLevel = []

For loop (i = 0 to 1):
  i = 0:
    node = queue.poll() = 15
    currentLevel.add(15) → [15]

    15.left = null, skip
    15.right = null, skip

    queue = [7]

  i = 1:
    node = queue.poll() = 7
    currentLevel.add(7) → [15, 7]

    7.left = null, skip
    7.right = null, skip

    queue = []

Add currentLevel to result → [[3], [9, 20], [15, 7]]

State:
  queue = []
  result = [[3], [9, 20], [15, 7]]

═══════════════════════════════════════
DONE! Queue is empty.
═══════════════════════════════════════

FINAL RESULT: [[3], [9, 20], [15, 7]]

🔍 Detailed Dry Run - DFS Approach

Tree:
       1
      / \
     2   3

Complete DFS Recursion:

CALL STACK VISUALIZATION:

Level 0: dfs(1, 0, [])
│
├─ node = 1, level = 0, result = []
├─ level == result.size()? 0 == 0 → YES
├─ Create new list: result = [[]]
├─ Add 1 to result[0]: result = [[1]]
│
├─ LEFT: dfs(2, 1, [[1]]) ──────────────────┐
│                                            │
│  Level 1: dfs(2, 1, [[1]])                │
│  │                                         │
│  ├─ node = 2, level = 1                  │
│  ├─ level == result.size()? 1 == 1 → YES │
│  ├─ Create new list: result = [[1], []]  │
│  ├─ Add 2: result = [[1], [2]]           │
│  │                                         │
│  ├─ LEFT: dfs(null, 2, [[1], [2]])       │
│  │  └─ return (null)                     │
│  │                                         │
│  ├─ RIGHT: dfs(null, 2, [[1], [2]])      │
│  │  └─ return (null)                     │
│  │                                         │
│  └─ return                                │
│                                            │
├─ After left child processed               │
├─ result = [[1], [2]]                      │
│                                            │
├─ RIGHT: dfs(3, 1, [[1], [2]]) ───────────┐
│                                            │
│  Level 1: dfs(3, 1, [[1], [2]])          │
│  │                                         │
│  ├─ node = 3, level = 1                  │
│  ├─ level == result.size()? 1 == 2 → NO  │
│  ├─ List exists! Just add                │
│  ├─ Add 3: result = [[1], [2, 3]]        │
│  │                                         │
│  ├─ LEFT: dfs(null, 2, [[1], [2, 3]])    │
│  │  └─ return (null)                     │
│  │                                         │
│  ├─ RIGHT: dfs(null, 2, [[1], [2, 3]])   │
│  │  └─ return (null)                     │
│  │                                         │
│  └─ return                                │
│                                            │
└─ FINAL: result = [[1], [2, 3]]           │

Result: [[1], [2, 3]]

📊 BFS vs DFS Comparison

BFS (Queue-based):

✓ Natural for level order
✓ Processes levels in order
✓ Iterative (no recursion)
✓ Easy to understand for this problem
✗ Requires queue data structure

Code simplicity: ⭐⭐⭐⭐⭐
Intuitiveness: ⭐⭐⭐⭐⭐

Use when: Level-by-level processing needed

DFS (Recursion with level tracking):

✓ Uses recursion (elegant)
✓ No extra data structure needed
✗ Less intuitive for level order
✗ Adds nodes out of level order (but still correct!)

Code simplicity: ⭐⭐⭐
Intuitiveness: ⭐⭐

Use when: Want to avoid queue, prefer recursion

When to Use Each:

For Level Order problems:
  → Use BFS (Queue)
  → It's the natural choice!

For Depth problems:
  → Use DFS (Recursion)
  → Natural for going deep

For other tree problems:
  → Either works
  → Choose based on problem needs

📊 Complexity Analysis

BFS Solution:

Time Complexity: O(n) 

Where n = number of nodes

Visit each node exactly once
At each node: O(1) operations
Total: n × O(1) = O(n)

All nodes must be visited!

Space Complexity: O(n) 

Queue: O(w) where w = maximum width
Result: O(n) for storing all nodes

Width calculation:
  - Worst case: Complete tree last level
  - Last level has n/2 nodes
  - So w = O(n)

Total: O(n) + O(n) = O(n)

DFS Solution:

Time Complexity: O(n) 

Same as BFS - visit each node once

Space Complexity: O(n) 

Recursion stack: O(h) where h = height
Result: O(n)

Best case (balanced): O(log n) + O(n) = O(n)
Worst case (skewed): O(n) + O(n) = O(n)

Total: O(n)

⚠️ Common Mistakes

Mistake 1: Not Using levelSize

// ❌ WRONG - Can't separate levels!
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    result.add(node.val);  // Where does this level end?

    if (node.left != null) queue.offer(node.left);
    if (node.right != null) queue.offer(node.right);
}

// Result: [3, 9, 20, 15, 7] - flat list, not levels!

// ✓ CORRECT - Use levelSize
while (!queue.isEmpty()) {
    int levelSize = queue.size();  // Critical!
    List<Integer> currentLevel = new ArrayList<>();

    for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();
        currentLevel.add(node.val);
        // ...
    }

    result.add(currentLevel);
}

Mistake 2: Wrong Loop Condition

// ❌ WRONG - Using queue.size() in loop condition
while (!queue.isEmpty()) {
    // Size changes as we add children!
    for (int i = 0; i < queue.size(); i++) {
        TreeNode node = queue.poll();
        // ...
        queue.offer(node.left);   // Size increased!
        queue.offer(node.right);  // Size increased again!
    }
}

// Loop runs wrong number of times!

// ✓ CORRECT - Capture size before loop
int levelSize = queue.size();  // Fixed value!
for (int i = 0; i < levelSize; i++) {
    // Process exactly levelSize nodes
}

Mistake 3: Not Creating New List for Each Level

// ❌ WRONG - Reusing same list
List<Integer> currentLevel = new ArrayList<>();

while (!queue.isEmpty()) {
    int levelSize = queue.size();

    for (int i = 0; i < levelSize; i++) {
        currentLevel.add(node.val);
    }

    result.add(currentLevel);
    currentLevel.clear();  // Clears in result too!
}

// All levels reference same list!
// After clear(), all are empty!

// ✓ CORRECT - New list for each level
while (!queue.isEmpty()) {
    List<Integer> currentLevel = new ArrayList<>();  // New!
    // ...
    result.add(currentLevel);
}

Mistake 4: DFS - Wrong Level Check

// ❌ WRONG - Creating lists incorrectly
private void dfs(TreeNode node, int level, List<List<Integer>> result) {
    if (node == null) return;

    if (result.size() < level) {  // Wrong comparison!
        result.add(new ArrayList<>());
    }

    result.get(level).add(node.val);
    // ...
}

// Creates too many or too few lists!

// ✓ CORRECT - Check if level == size
if (level == result.size()) {  // Exactly right!
    result.add(new ArrayList<>());
}

Mistake 5: Forgetting Null Check for Children

// ❌ WRONG - Adding null to queue
TreeNode node = queue.poll();
queue.offer(node.left);   // Might be null!
queue.offer(node.right);  // Might be null!

// Queue fills with nulls!
// NullPointerException when processing!

// ✓ CORRECT - Check before adding
if (node.left != null) {
    queue.offer(node.left);
}
if (node.right != null) {
    queue.offer(node.right);
}

🎯 Pattern Recognition - Level-Based Problems

Core Pattern: Level Order Processing

Template for level-based problems:

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

while (!queue.isEmpty()) {
    int levelSize = queue.size();

    // Process current level
    for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();

        // Do something with node
        process(node);

        // Add children for next level
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }

    // After level processing
    doSomethingAfterLevel();
}

1. Binary Tree Zigzag Level Order 

Same as level order but alternate direction
  Level 0: left to right
  Level 1: right to left
  Level 2: left to right

Use same BFS + reverse alternate levels

2. Binary Tree Right Side View 

Return rightmost node of each level

Use level order traversal
Only return last node of each level

3. Average of Levels 

Calculate average value per level

Use level order traversal
Calculate sum / count for each level

4. Minimum Depth (Problem 134) 

BFS is BETTER than DFS!

First leaf found = minimum depth
Early return optimization

5. Maximum Width of Binary Tree 

Find maximum width of any level

Use level order with position tracking
Calculate max width per level

When to Use This Pattern:

✓ "Level" in problem statement
✓ "Layer" or "row" mentioned
✓ "Left to right at each level"
✓ Need to process tree horizontally
✓ Level-based calculations

📝 Quick Revision Notes

🎯 Core Concept

Level Order = BFS = Visit tree level by level. Use Queue (FIFO). Critical pattern: capture levelSize = queue.size() BEFORE loop, process exactly that many nodes. This separates levels. Add children to queue for next level. Alternative: DFS with level tracking (less natural). Queue is standard for level-based problems.

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr[0] == null) {
            return null;
        }

        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            TreeNode current = queue.poll();

            // Process left child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.left = new TreeNode(arr[i]);
                    queue.offer(current.left);
                }
                i++;
            }

            // Process right child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.right = new TreeNode(arr[i]);
                    queue.offer(current.right);
                }
                i++;
            }
        }

        return root;
    }

    public static void print(TreeNode root) {
        if (root == null) {
            System.out.println("[]");
            return;
        }

        List<String> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                result.add(String.valueOf(node.val));
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                result.add("null");
            }
        }

        while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
            result.remove(result.size() - 1);
        }

        System.out.println(result);
    }    
}

class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) {
      return res;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
      List<Integer> temp = new ArrayList<>();

      // process the current level.
      int size = queue.size();
      for(int i = 0; i < size; i++) {
        TreeNode curr = queue.poll();
        temp.add(curr.val);

        if(curr.left != null) {
          queue.offer(curr.left);
        }

        if(curr.right != null) {
          queue.offer(curr.right);
        }
      }

      res.add(new ArrayList<>(temp));
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.levelOrder(TreeNode.buildTree(new Integer[] {3,9,20,null,null,15,7})));
    System.out.println(s.levelOrder(TreeNode.buildTree(new Integer[] {1})));
    System.out.println(s.levelOrder(TreeNode.buildTree(new Integer[] {})));
  }
}


private void dfs(TreeNode node, int level, List<List<Integer>> result) {
    if (node == null) return;

    if (level == result.size()) {
        result.add(new ArrayList<>());
    }

    result.get(level).add(node.val);
    dfs(node.left, level + 1, result);
    dfs(node.right, level + 1, result);
}

🔑 Key Insights

BFS vs DFS: 

BFS (Breadth-First):
  - Uses Queue (FIFO)
  - Goes WIDE (level by level)
  - Natural for level order
  - Example: 1 → 2 → 3 → 4 → 5

DFS (Depth-First):
  - Uses Stack (or recursion)
  - Goes DEEP (to leaves first)
  - Natural for inorder/preorder/postorder
  - Example: 1 → 2 → 4 → 5 → 3

Different tools for different jobs! 🔧

The levelSize Pattern: 

Why capture size before loop?

while (!queue.isEmpty()) {
    int levelSize = queue.size();  ← Snapshot!

    for (i = 0 to levelSize) {
        // Add children to queue
        // Queue grows, but loop uses fixed levelSize
    }
}

Without snapshot:
  - Queue size changes during loop
  - Can't separate levels
  - Processes wrong number of nodes

This is the KEY to level-order! 🔑

Queue = Level Order: 

Queue properties:
  - FIFO (First In, First Out)
  - Like a line at a store
  - First person to arrive → First served

Perfect for BFS:
  - Process parent before children
  - All level N before level N+1
  - Natural ordering!

Stack (DFS) = LIFO → Goes deep
Queue (BFS) = FIFO → Goes wide

🎪 Memory Aid

"Queue for levels, Stack for depths!"
"Capture size before the loop!"
"BFS goes wide, DFS goes deep!"
"FIFO for layers, LIFO for divers!" ✨

⚠️ Don't Forget

  • Capture levelSize first (before loop modifies queue!)
  • New list per level (don't reuse same list!)
  • Check null before offering (don't add null to queue!)
  • Use Queue not Stack (BFS needs FIFO!)
  • Process entire level (exactly levelSize iterations!)
  • BFS is natural (don't force DFS for level problems!)

🎉 Congratulations!

You've mastered BFS and level-order traversal!

What You Learned:

✅ BFS concept - Breadth-first search
✅ Queue usage - FIFO for level processing
✅ Level separation - The levelSize pattern
✅ BFS vs DFS - When to use each
✅ Two approaches - Queue-based and DFS-based
✅ Level-order template - Reusable pattern

The Fundamental Algorithms:

You now know BOTH traversal types:

DFS (Problem 139):
  - Inorder, Preorder, Postorder
  - Uses Stack or recursion
  - Goes DEEP

BFS (Problem 140):
  - Level Order
  - Uses Queue
  - Goes WIDE

These are THE TWO ways to traverse trees! 🌳
Every tree algorithm uses one of these!

Pattern Evolution:

Problems 131-138:
  ✓ Used DFS implicitly
  ✓ Recursion-based
  ✓ Depth-first thinking

Problem 139:
  ✓ Explicit DFS patterns
  ✓ Three traversal orders
  ✓ Recursive and iterative

Problem 140:
  ✓ BFS introduction!
  ✓ Queue-based traversal
  ✓ Level-by-level thinking

Foundation complete! 🏗️

Next Steps:

Perfect problems to apply BFS: - Zigzag Level Order (same pattern!) - Right Side View (last of each level!) - Average of Levels (level calculations!) - Minimum Depth (BFS early return!)

You now have BOTH traversal tools! 🧰🌳✨