BFS vs DFS in Java: Two Traversals, One Decision

I was prepping for a system design interview a few months back and the interviewer asked me to find the shortest path between two nodes. I coded up DFS, explained it confidently, and then he asked “but is that actually the shortest?” It wasn’t. I’d used the wrong traversal and didn’t even realize it.

That’s the thing about BFS and DFS, they look similar, they both visit every node, but the order they do it in changes everything about what they’re good for. If you mix them up, your code compiles, runs, and gives you the wrong answer silently.

BFS vs DFS: What’s Actually Different?

Both traverse every reachable node in a graph. The difference is the order in which they visit nodes: and that order changes everything.

         A
       /   \
      B     C
     / \   / \
    D   E F   G

BFS order (level by level): A, B, C, D, E, F, G
DFS order (deep first):     A, B, D, E, C, F, G

BFS explores neighbors first: it fans out level by level. DFS goes as deep as possible down one path before backtracking.

How BFS Works

BFS uses a queue (FIFO). It visits a node, then queues all its unvisited neighbors. The next node to visit is always the one that’s been waiting the longest.

Queue visual:

Step 1: [A]          visit A, enqueue B, C
Step 2: [B, C]       visit B, enqueue D, E
Step 3: [C, D, E]    visit C, enqueue F, G
Step 4: [D, E, F, G] visit D
Step 5: [E, F, G]    visit E
Step 6: [F, G]       visit F
Step 7: [G]          visit G
Step 8: []           done

Visit order: A, B, C, D, E, F, G

The thing that makes BFS special is that it discovers nodes in order of their distance from the start. Everything at distance 1 is visited before anything at distance 2, and so on. That’s why BFS finds the shortest path in an unweighted graph: it literally can’t reach a farther node before a closer one.

How DFS Works

DFS uses a stack (LIFO): either explicitly or via recursion. It plunges down a path until it hits a dead end, then backtracks.

Stack visual (iterative):

Step 1: [A]          pop A, push C, B
Step 2: [B, C]       pop B, push E, D
Step 3: [D, E, C]    pop D
Step 4: [E, C]       pop E
Step 5: [C]          pop C, push G, F
Step 6: [F, G]       pop F
Step 7: [G]          pop G
Step 8: []           done

Visit order: A, B, D, E, C, F, G

DFS goes deep before wide. It’s memory-efficient for deep graphs and is the natural choice when the solution lies far from the root. I think of it like exploring a maze by always taking the leftmost path, you go all the way in before you try anything else.

Java Implementation: The Graph

Both algorithms share the same graph representation. An adjacency list is almost always the right choice, it’s memory-efficient and gives O(1) neighbor access.

import java.util.*;

public class Graph {
    private final Map<String, List<String>> adjacencyList = new HashMap<>();

    public void addNode(String node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(String from, String to) {
        adjacencyList.get(from).add(to);
        adjacencyList.get(to).add(from); // undirected graph
    }

    public List<String> getNeighbors(String node) {
        return adjacencyList.getOrDefault(node, List.of());
    }

    public Set<String> getNodes() {
        return adjacencyList.keySet();
    }
}

BFS: Iterative Implementation

BFS is always iterative. A queue and a visited set are all you need.

import java.util.*;

public class BFS {

    public static List<String> traverse(Graph graph, String start) {
        List<String> visitOrder = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            String current = queue.poll();
            visitOrder.add(current); // process the node

            for (String neighbor : graph.getNeighbors(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return visitOrder;
    }
}

I’ve seen this bug more times than I can count: people mark a node as visited when they poll it, not when they enqueue it. That means the same node can get queued multiple times from different parents, and on a dense graph your queue explodes. Mark on enqueue. Always.

BFS with Level Tracking

Often you need to know the depth. This variant processes the graph one level at a time:

public static List<List<String>> traverseByLevel(Graph graph, String start) {
    List<List<String>> levels = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Queue<String> queue = new LinkedList<>();

    queue.add(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<String> currentLevel = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            String current = queue.poll();
            currentLevel.add(current);

            for (String neighbor : graph.getNeighbors(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        levels.add(currentLevel);
    }

    return levels;
}

BFS Shortest Path (Unweighted Graphs)

Since BFS visits nodes in order of distance, adding a parent map gives you the shortest path:

public static List<String> shortestPath(Graph graph, String start, String target) {
    Set<String> visited = new HashSet<>();
    Map<String, String> parent = new HashMap<>();
    Queue<String> queue = new LinkedList<>();

    queue.add(start);
    visited.add(start);
    parent.put(start, null);

    while (!queue.isEmpty()) {
        String current = queue.poll();

        if (current.equals(target)) {
            return reconstructPath(parent, target);
        }

        for (String neighbor : graph.getNeighbors(current)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                parent.put(neighbor, current);
                queue.add(neighbor);
            }
        }
    }

    return List.of(); // no path exists
}

private static List<String> reconstructPath(Map<String, String> parent, String target) {
    List<String> path = new LinkedList<>();
    String current = target;

    while (current != null) {
        path.addFirst(current);
        current = parent.get(current);
    }

    return path;
}

DFS: Recursive Implementation

DFS feels most natural with recursion. The call stack acts as the DFS stack for free.

import java.util.*;

public class DFS {

    public static List<String> traverse(Graph graph, String start) {
        List<String> visitOrder = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        dfsRecursive(graph, start, visited, visitOrder);
        return visitOrder;
    }

    private static void dfsRecursive(
        Graph graph,
        String current,
        Set<String> visited,
        List<String> visitOrder
    ) {
        visited.add(current);
        visitOrder.add(current); // process the node (pre-order)

        for (String neighbor : graph.getNeighbors(current)) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(graph, neighbor, visited, visitOrder);
            }
        }
    }
}

DFS: Iterative Implementation

Sometimes you want DFS without recursion, either to avoid stack overflow on deep graphs or because you prefer explicit control:

public static List<String> traverseIterative(Graph graph, String start) {
    List<String> visitOrder = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Deque<String> stack = new ArrayDeque<>();

    stack.push(start);

    while (!stack.isEmpty()) {
        String current = stack.pop();

        if (visited.contains(current)) continue;

        visited.add(current);
        visitOrder.add(current);

        // Push neighbors in reverse order to match recursive behavior.
        // Without this, the visit order differs but is still a valid DFS.
        List<String> neighbors = graph.getNeighbors(current);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            String neighbor = neighbors.get(i);
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }

    return visitOrder;
}

DFS Cycle Detection (Directed Graph)

DFS can detect cycles by tracking nodes currently in the recursion stack:

public static boolean hasCycle(Graph graph) {
    Set<String> visited = new HashSet<>();
    Set<String> inStack = new HashSet<>();

    for (String node : graph.getNodes()) {
        if (!visited.contains(node)) {
            if (hasCycleFrom(graph, node, visited, inStack)) {
                return true;
            }
        }
    }

    return false;
}

private static boolean hasCycleFrom(
    Graph graph,
    String current,
    Set<String> visited,
    Set<String> inStack
) {
    visited.add(current);
    inStack.add(current);

    for (String neighbor : graph.getNeighbors(current)) {
        if (!visited.contains(neighbor)) {
            if (hasCycleFrom(graph, neighbor, visited, inStack)) {
                return true;
            }
        } else if (inStack.contains(neighbor)) {
            // Back edge found - cycle exists
            return true;
        }
    }

    inStack.remove(current); // backtrack
    return false;
}

DFS Topological Sort

For directed acyclic graphs (DAGs), DFS gives you a topological ordering, nodes listed so every edge goes left to right. I had to implement this once for a build system that needed to figure out the right order to compile modules. DFS post-order reversed is surprisingly elegant for it:

public static List<String> topologicalSort(Graph graph) {
    List<String> order = new ArrayList<>();
    Set<String> visited = new HashSet<>();

    for (String node : graph.getNodes()) {
        if (!visited.contains(node)) {
            topologicalDfs(graph, node, visited, order);
        }
    }

    Collections.reverse(order); // post-order reversed = topological order
    return order;
}

private static void topologicalDfs(
    Graph graph,
    String current,
    Set<String> visited,
    List<String> order
) {
    visited.add(current);

    for (String neighbor : graph.getNeighbors(current)) {
        if (!visited.contains(neighbor)) {
            topologicalDfs(graph, neighbor, visited, order);
        }
    }

    order.add(current); // post-order: add after children
}

BFS vs DFS: Side-by-Side

When to Use BFS

BFS is your go-to when:

• You need the shortest path in an unweighted graph. BFS visits nodes in order of distance, so the first time you reach a target is guaranteed to be via the shortest path. Word ladder: minimum moves in a grid: degrees of separation on a social network.
• You need level-order traversal. Nodes grouped by depth: printing a binary tree level by level: finding all nodes at distance K.
• The solution is probably close to the start. BFS searches locally first. If the answer is nearby: BFS finds it fast without wandering deep into the graph.
• You’re searching a web of relationships. Friend recommendations: “people you may know,” finding the closest connection between two people.

// Find the minimum number of moves in a grid maze
// Shortest transformation sequence (word ladder)
// Rotting oranges - spread level by level
// Find all nodes K distance away in a tree
// Check if a binary tree is complete

When to Use DFS

DFS shines when:

• You need to explore the entire search space. Puzzle solving: constraint satisfaction: generating all subsets or permutations. DFS exhaustively visits every branch.
• The solution is deep. If you suspect the answer lies far from the root: DFS gets there without the memory overhead of BFS.
• You’re doing backtracking. N-Queens, Sudoku: maze generation. DFS naturally unwinds the call stack when a path fails: returning you to the last decision point.
• You need cycle detection. DFS with a recursion stack detects cycles in directed graphs cleanly.
• You need topological ordering. Build systems: dependency resolution: course prerequisite chains. DFS post-order reversed gives you a valid topological sort.
• You need to discover graph structure. Connected components, bridges: articulation points: strongly connected components (Kosaraju’s or Tarjan’s).

// Generate all valid parentheses combinations
// N-Queens placement
// Find all paths from source to target
// Check if a binary tree is balanced
// Serialize / deserialize a binary tree
// Detect cycle in a directed graph
// Count connected components
// Solve a Sudoku puzzle

How I Decide Between BFS and DFS

When I’m staring at a graph problem and not sure which to use, I ask myself three questions:

1. Do I need the shortest path in an unweighted graph?
   Yes: Use BFS.
   No:  Continue.

2. Am I searching a very wide graph where memory matters?
   Yes: Use DFS (or iterative deepening DFS).
   No:  Continue.

3. Is the solution likely deep, or am I doing exhaustive search?
   Yes: Use DFS.
   No:  Use BFS (it's usually more intuitive and safer).

Honestly, if I’m not sure, I reach for BFS first. It’s harder to mess up, you don’t accidentally go down an infinite path, and the code is almost identical to DFS anyway.

Common Pitfalls

BFS: Forgetting to Mark Visited on Enqueue

// [ ] Wrong: mark on poll - leads to duplicates
queue.add(start);
while (!queue.isEmpty()) {
    String node = queue.poll();
    visited.add(node);          // too late
    for (String neighbor : graph.getNeighbors(node)) {
        if (!visited.contains(neighbor)) {
            queue.add(neighbor); // neighbor might already be in queue
        }
    }
}

// [x] Correct: mark on enqueue
queue.add(start);
visited.add(start);             // immediately
while (!queue.isEmpty()) {
    String node = queue.poll();
    for (String neighbor : graph.getNeighbors(node)) {
        if (!visited.contains(neighbor)) {
            visited.add(neighbor); // before it enters the queue
            queue.add(neighbor);
        }
    }
}

DFS: Stack Overflow on Deep Graphs

Recursive DFS crashes when the graph is deeper than the call stack limit (typically ~10,000 frames in Java). I hit this once on a graph problem with a 50,000-node chain and spent way too long debugging before realizing it was just a stack overflow. Switch to the iterative version or increase the stack size:

java -Xss4m Main    # 4 MB stack size instead of default 1 MB

DFS: Not Handling Disconnected Graphs

Both BFS and DFS only visit nodes reachable from the start. If your graph has disconnected components, wrap the call in a loop:

for (String node : graph.getNodes()) {
    if (!visited.contains(node)) {
        traverse(graph, node); // starts fresh from each unvisited component
    }
}

What I Took Away

After that interview fiasco, I started thinking about BFS and DFS less as “two algorithms” and more as “two search strategies.” BFS is breadth-first: check everything close before going far. DFS is depth-first: commit to a path and see where it goes. That framing makes it obvious which one fits.

BFS finds the shortest path. DFS explores everything. Match that to your goal and you’ll pick right almost every time.

Pro Tip: If you need the shortest path but the graph is too wide for BFS’s memory, use Iterative Deepening DFS (IDDFS). It runs DFS with a depth limit, increases the limit each iteration, and combines DFS’s O(depth) memory with BFS’s shortest-path guarantee. It does repeat work, but the overhead is surprisingly small: the final level dominates the total node count in most graphs.