Breadth-First Search

Level-order traversal with guarantees DFS cannot make.

Context

Breadth-First Search (BFS) is a traversal algorithm that explores nodes level by level. All nodes at depth d are processed before any node at depth d + 1.

Unlike Depth-First Search, which dives deep into a single branch, BFS expands outward uniformly from the root. This makes BFS especially valuable when distance matters, not just reachability.

BFS is typically implemented using a Queue, while DFS relies on a Stack (either explicitly or via recursion).

A practical implication of this difference is safety: DFS implemented recursively risks stack overflow on deep or skewed structures, whereas BFS uses heap-allocated memory for its queue and is therefore more predictable for large or adversarial inputs.

Core idea

• Maintain a queue of nodes to visit
• Initialise the queue with the starting (root) node
• While the queue is not empty:
  • Dequeue the next node
  • Process it (e.g. compare its value with the target)
  • Enqueue its children (left, then right)

The key invariant: Nodes are visited in increasing order of depth.

Implementation

public class BinaryNode<T> {
    private T value;
    private BinaryNode<T> left;
    private BinaryNode<T> right;
    
    // getters, setters, constructors omitted for brevity
}

public class BreadthFirstSearch {
    public static boolean find(BinaryNode<T> head, T needle) {
        if (head == null) return false;
    
        Queue<BinaryNode<T>> queue = new LinkedList<>();
        queue.add(head);
        
        while (!queue.isEmpty()) {
            var current = queue.poll();
            
            if (current.getValue().equals(needle)) return true;
            
            if (current.getLeft() != null) queue.add(current.getLeft());
            if (current.getRight() != null) queue.add(current.getRight());
        }
        
        return false;
    }
}