Understanding BFS vs DFS — Advanced Optimization

CPU Cache and Memory Access Patterns

Modern CPUs have multiple levels of cache (L1, L2, L3) that are much faster than main memory. The key insight:

L1 Cache:  ~1-4 cycles latency,   ~100 GB/s bandwidth
L2 Cache:  ~10-15 cycles latency,  ~50 GB/s bandwidth
L3 Cache:  ~40-50 cycles latency,  ~20 GB/s bandwidth
Main RAM:  ~100-200 cycles latency, ~10 GB/s bandwidth
              

The more cache-friendly your algorithm, the faster it runs. This is where BFS and DFS differ significantly.

BFS: Better Cache Locality (Usually)

BFS processes nodes level by level. If nodes are stored in an array (common in heaps or when using array-based tree representations), adjacent nodes in memory are often processed together:

Level 0: [Node 0]           ← Process first
Level 1: [Node 1, Node 2]   ← Process together (cache friendly!)
Level 2: [Node 3, 4, 5, 6]  ← Process together (cache friendly!)
              

BFS advantage: When nodes are stored contiguously, BFS visits nearby memory locations in succession, maximizing cache hits. Each cache line (typically 64 bytes) can hold multiple tree nodes.

DFS: Pointer Chasing Problem

DFS jumps around memory following pointers. Each node access might require a cache miss because nodes are typically allocated non-contiguously:

DFS traversal: Node 0 → Node 1 → Node 3 → backtrack → Node 4 → ...
Memory addresses: 0x1000 → 0x2500 → 0x4000 → ... → 0x3000
                         ↑           ↑              ↑
                      Random memory access pattern = cache misses!
              

DFS challenge: Each pointer dereference is a potential cache miss. On a modern CPU, a cache miss can be 100x slower than a cache hit.

Real-World Performance Benchmarks

On a balanced binary tree with 10 million nodes (tested on Intel i7-12700K):

Branch Prediction

Modern CPUs use branch prediction to guess which way code will go. Mispredictions cost ~15-20 cycles.

// DFS recursion creates unpredictable branches
if (node.left) traverse(node.left);  // Will this execute?
if (node.right) traverse(node.right); // Will this execute?

// BFS with level processing is more predictable
int levelSize = queue.size();        // Known count
for (int i = 0; i < levelSize; i++) // Predictable loop
              

BFS loops have more predictable patterns, allowing the CPU's branch predictor to work more effectively.

Optimization Techniques

// Instead of individual allocations
TreeNode* nodes = new TreeNode[totalNodes];  // Contiguous!

// Heap-style array representation
// Parent of i: (i-1)/2
// Left child: 2i+1, Right child: 2i+2
int tree[] = {root, left1, right1, left2, ...};

// IDDFS: DFS with increasing depth limits
for (int depth = 0; depth < maxDepth; depth++) {
    if (dfs_with_limit(root, depth, target)) return depth;
}

When to Choose What (Expert Edition)

Real-World Use Cases