← Back to All Patterns

Tree BFS (Breadth-First Search)

🌳 Tree BFS Animation - Level Order Traversal

1
2
3
4
5
6

Queue (FIFO):

Front →
1
← Back

Visited Order:

Start: Add root (1) to queue

Step 1 of 7
Current
In Queue
Visited ✓

🎯 Explain Like I'm 5...

Imagine a family tree where grandpa is at the top, parents are in the middle, and kids are at the bottom!

🏠 Floor by Floor (BFS = Breadth-First):

  • • Floor 1: Visit Grandpa first! 👴
  • • Floor 2: Then visit BOTH parents (Mom and Dad) from left to right! 👨👩
  • • Floor 3: Finally visit ALL the kids from left to right! 👧👦👶

You finish one WHOLE floor before going to the next floor down!

🚀 The Secret: Use a waiting line (queue)! Visit someone, put their children in line, then visit the next person in line. It's like taking turns at the playground - first come, first served! 🎢

When Should You Use This Pattern?

  • ✓Level-order traversal (visit level by level)
  • ✓Finding minimum depth of tree
  • ✓Zigzag level order traversal
  • ✓Finding nodes at each level

📝 Example 1: Level Order Traversal

Return the level order traversal of a tree's nodes (level by level, left to right).

LevelOrderTraversal.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}
public class LevelOrderTraversal {
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // Use queue for BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            // Process all nodes at current level
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                // Add children to queue for next level
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(currentLevel);
        }
        return result;
    }
    public static void main(String[] args) {
        // Create tree:     1
        //                 / \
        //                2   3
        //               / \   \
        //              4   5   6
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        List<List<Integer>> result = levelOrder(root);
        System.out.println("Level order: " + result);
        // Output: [[1], [2, 3], [4, 5, 6]]
    }
}

📝 Example 2: Zigzag Level Order

Return zigzag level order: left-to-right, then right-to-left, alternating.

ZigzagTraversal.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.*;
public class ZigzagTraversal {
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                // Add to front or back based on direction
                if (leftToRight) {
                    currentLevel.add(node.val);
                } else {
                    currentLevel.add(0, node.val);  // Add to front
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(currentLevel);
            leftToRight = !leftToRight;  // Flip direction
        }
        return result;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        List<List<Integer>> result = zigzagLevelOrder(root);
        System.out.println("Zigzag order: " + result);
        // Output: [[1], [3, 2], [4, 5, 6]]
    }
}

📝 Example 3: Minimum Depth of Tree

Find the minimum depth (shortest path from root to any leaf node).

MinimumDepth.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;
public class MinimumDepth {
    public static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                // If we find a leaf, return current depth
                if (node.left == null && node.right == null) {
                    return depth;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            depth++;  // Processed one level
        }
        return depth;
    }
    public static void main(String[] args) {
        // Tree:     1
        //          / \
        //         2   3
        //        /
        //       4
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        System.out.println("Minimum depth: " + minDepth(root));
        // Output: 2 (path: 1 -> 3)
    }
}

🔑 Key Points to Remember

  • 1️⃣Always use a Queue for BFS (FIFO)
  • 2️⃣Track level size to process level by level
  • 3️⃣Time Complexity: O(n) - visit each node once
  • 4️⃣Space Complexity: O(n) - queue can hold up to n/2 nodes

💪 Practice Problems

  • • Binary Tree Level Order Traversal II (bottom-up)
  • • Average of Levels in Binary Tree
  • • Binary Tree Right Side View
  • • Connect Level Order Siblings
  • • Maximum Depth of Binary Tree