Java and Breadth-First Tree Traversal

Breadth-First Search (BFS) is a fundamental traversal algorithm used to explore tree structures level by level. Unlike D

Breadth-First Search (BFS) is a fundamental traversal algorithm used to explore tree structures level by level. Unlike Depth-First Search (DFS), which dives deep into a branch before backtracking, BFS expands outward from the root, visiting all nodes at the current depth before moving on to the nodes at the next depth level.

Think of BFS as a ripple in a pond: the search starts at a single point (the root) and spreads uniformly across each concentric layer. This "wide" approach makes BFS particularly effective for problems related to proximity, distance, and level-based organization.

The Core Mechanism: The Queue

The defining characteristic of BFS is its reliance on a Queue data structure. Because BFS must process nodes in the exact order they are discovered to maintain the level-by-level property, it utilizes the First-In-First-Out (FIFO) principle.

When we visit a node, we "enqueue" (add) its children to the back of the queue. Because the queue processes elements from the front, all nodes at the current level will be removed and processed before any of the newly added children (the next level) can be reached.

Implementing BFS in Java

To implement BFS in Java, we first need a standard definition for a tree node.

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

    TreeNode(int val) {
        this.val = val;
    }
}

Choosing the Right Queue Implementation

In Java, the Queue is an interface, meaning we must instantiate a concrete class. While LinkedList is a common choice, ArrayDeque is generally recommended for BFS implementations. ArrayDeque is more memory-efficient and typically offers better performance as a queue because it is backed by a resizable array rather than a chain of linked nodes.

Note: ArrayDeque does not permit null elements. Since we typically check for null before adding nodes to the queue in tree traversals, this is rarely an issue in practice.

Commonly used methods include:

  • offer(e): Adds an element to the end of the queue.
  • poll(): Removes and returns the head of the queue.
  • peek(): Retrieves, but does not remove, the head of the queue.
  • isEmpty(): Returns true if the queue contains no elements.

Basic Implementation: Simple Level-Order Traversal

The most straightforward application of BFS is a simple level-order traversal, where we visit every node and collect their values into a single list.

import java.util.*;

public List<Integer> bfs(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

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

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        result.add(node.val);

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

    return result;
}

Advanced Implementation: Grouping Nodes by Level

In many real-world scenarios, simply visiting nodes is not enough; we often need to distinguish between different levels (e.g., returning a list of lists where each sub-list represents one level).

The trick to achieving this is to capture the queue size at the beginning of each level's iteration. Since the queue size tells us exactly how many nodes are currently in the "current" level, we can use a loop to process only those nodes before moving to the next level.

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

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

    while (!queue.isEmpty()) {
        // Capture the number of nodes at the current level
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>(levelSize);

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

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        // Add the completed level to the final result
        result.add(currentLevel);
    }

    return result;
}

Example Walkthrough:
For a tree structured as follows:

        1
       / \
      2   3
     / \   \
    4   5   6

The output would be: [[1], [2, 3], [4, 5, 6]].

Complexity Analysis

Understanding the efficiency of BFS is crucial for optimizing large-scale applications.

  • Time Complexity: $O(n)$
    Every node in the tree is visited exactly once. Each node is added to the queue once and removed from the queue once, resulting in linear time complexity relative to the number of nodes $n$.

  • Space Complexity: $O(w)$
    The space complexity is determined by the maximum width ($w$) of the tree, which represents the maximum number of nodes stored in the queue at any given time.

    • In a perfectly balanced binary tree, the last level contains approximately $n/2$ nodes, making the worst-case space complexity $O(n)$.
    • In a skewed tree (essentially a linked list), the width is 1, making the space complexity $O(1)$.

Practical Application: Finding the Minimum Depth

One of the most powerful advantages of BFS is its ability to find the minimum depth of a tree (the number of nodes along the shortest path from the root node down to the nearest leaf node).

While DFS can solve this, it might explore an extremely deep branch before ever finding a leaf node that is much closer to the root. BFS, however, explores level by level; the moment we encounter the first leaf node, we can immediately return the current depth, potentially saving significant computation time.

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    int depth = 1;

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

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

            // The first leaf node we encounter defines the minimum 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++;
    }

    return depth;
}

Summary

Mastering BFS in Java requires a solid understanding of the Queue data structure and the "level-size" pattern. By using ArrayDeque for performance and carefully managing the queue size during iterations, you can efficiently solve a variety of problems, including:

  • Level-order grouping for hierarchical data visualization.
  • Finding the shortest path in unweighted structures.
  • Determining tree properties, such as whether a tree is complete or finding its minimum depth.

While DFS is often easier to implement via recursion, BFS remains the superior choice for any problem where the "closest" or "shallowest" solution is the priority.