Bidirectional BFS

The Problem With Standard BFS

Consider LeetCode 127. Word Ladder. You are given a start word, an end word, and a dictionary of valid words. You need to find the shortest transformation sequence from start to end, where each step changes exactly one letter and every intermediate word must be in the dictionary. For example, transforming "hit" to "cog" through the dictionary ["hot", "dot", "dog", "lot", "log", "cog"] gives the chain hit -> hot -> dot -> dog -> cog, which has length 5.

This is a shortest-path problem on an unweighted graph, so BFS is the natural choice. But consider the scale of the search. If each word has length L and the alphabet has 26 letters, each word has up to $25L$ neighbors to check. In general, if the branching factor is $b$ and the shortest path has depth $d$, standard BFS explores $O(b^d)$ nodes before finding the target. For a branching factor of 50 and a path of depth 10, that is $50^{10} \approx 10^{17}$ nodes. Far too many.

The Core Idea: Search From Both Ends

Bidirectional BFS starts two simultaneous searches: one forward from the start node and one backward from the end node. Instead of one frontier expanding through $d$ levels, you get two frontiers each expanding through roughly $d/2$ levels. The search terminates as soon as the two frontiers meet.

The node count drops dramatically. Each direction explores $O(b^{d/2})$ nodes, so the total is $O(2 \cdot b^{d/2}) = O(b^{d/2})$. With our earlier numbers, that is $50^5 \approx 3 \times 10^8$, a reduction by a factor of $b^{d/2}$. This is the same "meet in the middle" principle used in other algorithms, applied to graph search.

The Algorithm

Maintain two sets representing the visited nodes from each direction, and two frontier sets representing the current wavefronts. At each step:

1. Pick the smaller frontier (this is critical for efficiency).
2. Expand every node in that frontier by one step, generating a new frontier.
3. If any newly generated node already exists in the other direction's visited set, the two searches have met. The total shortest path length is the sum of the depths from each side.
4. Otherwise, add the new frontier to its direction's visited set and repeat.

Expanding the smaller frontier ensures that the two search trees stay roughly balanced, minimizing the total number of nodes explored.

Walking Through Word Ladder

Start word: "hit". End word: "cog". Dictionary: {"hot", "dot", "dog", "lot", "log", "cog"}.

Step 0. Forward frontier: {"hit"}. Backward frontier: {"cog"}. Depth: 1.

Step 1. Forward frontier is smaller (tie, pick either). Expand "hit": change each letter to every possibility and check the dictionary. "hot" is valid. New forward frontier: {"hot"}. Forward visited: {"hit", "hot"}. Depth: 2.

Step 2. Both frontiers have size 1 (tie). Expand backward frontier {"cog"}: neighbors in dictionary are "dog" and "log". New backward frontier: {"dog", "log"}. Backward visited: {"cog", "dog", "log"}. Depth: 3.

Step 3. Forward frontier {"hot"} is smaller (size 1 vs 2). Expand "hot": neighbors are "dot" and "lot". New forward frontier: {"dot", "lot"}. Forward visited: {"hit", "hot", "dot", "lot"}. Depth: 4.

Step 4. Both frontiers have size 2. Expand backward frontier {"dog", "log"}. Neighbors of "dog": "dot" and "dog" -> "cog" (already visited). "dot" is in the forward visited set. The frontiers have met.

The total depth is 5 (the current depth counter). We explored roughly 10 nodes total. A unidirectional BFS would have explored the entire reachable graph.

Code: Word Ladder With Bidirectional BFS

from collections import defaultdict

def ladder_length(begin_word, end_word, word_list):
    word_set = set(word_list)
    if end_word not in word_set:
        return 0

    front = {begin_word}
    back = {end_word}
    visited = {begin_word, end_word}
    depth = 1

    while front and back:
        depth += 1
        # Always expand the smaller frontier
        if len(front) > len(back):
            front, back = back, front

        next_front = set()
        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    candidate = word[:i] + c + word[i+1:]
                    if candidate in back:
                        return depth
                    if candidate in word_set and candidate not in visited:
                        visited.add(candidate)
                        next_front.add(candidate)
        front = next_front

    return 0

The key details: front and back are the two frontier sets. Before expanding, we swap them if front is larger so we always expand the smaller one. For each word in the current frontier, we try all single-character mutations. If a mutation appears in the opposite frontier, the two searches have met and we return the depth. Otherwise, if the mutation is a valid unvisited word, we add it to the next frontier.

Using sets for both frontiers and the visited collection makes the membership checks $O(1)$, which is essential for performance.

Application: Open the Lock

LeetCode 752. Open the Lock is another natural fit. You have a lock with 4 circular dials, each showing digits 0-9. The lock starts at "0000" and you need to reach a target combination. Each move turns one dial one slot up or down (9 wraps to 0 and vice versa). Some combinations are "deadends" that lock the mechanism permanently. Find the minimum number of moves.

This is BFS on a graph where each node is a 4-digit string and each node has 8 neighbors (4 dials times 2 directions). The branching factor is 8 and the state space has $10^4 = 10000$ nodes. Bidirectional BFS helps because you know both the start ("0000") and the target.

def open_lock(deadends, target):
    dead = set(deadends)
    if "0000" in dead:
        return -1
    if target == "0000":
        return 0

    front = {"0000"}
    back = {target}
    visited = {"0000", target}
    depth = 0

    while front and back:
        depth += 1
        if len(front) > len(back):
            front, back = back, front

        next_front = set()
        for state in front:
            for i in range(4):
                d = int(state[i])
                for delta in (1, -1):
                    nd = (d + delta) % 10
                    candidate = state[:i] + str(nd) + state[i+1:]
                    if candidate in back:
                        return depth
                    if candidate not in visited and candidate not in dead:
                        visited.add(candidate)
                        next_front.add(candidate)
        front = next_front

    return -1

The structure is identical to Word Ladder. The only differences are how neighbors are generated (dial turns instead of letter substitutions) and the handling of deadends.

When Bidirectional BFS Works

Bidirectional BFS requires three conditions:

You must know the target state. The algorithm searches backward from the goal, so the goal must be a specific, known node. Word Ladder gives you the end word. Open the Lock gives you the target combination. If the problem says "find the nearest node satisfying some property" without specifying which node that is, you cannot search backward from it.

The graph must be unweighted (or uniformly weighted). Bidirectional BFS relies on both frontiers advancing at the same rate. If edges have different weights, the frontiers do not stay synchronized and meeting in the middle does not guarantee the shortest path. For weighted graphs, you would need bidirectional Dijkstra, which is significantly more complex.

The graph must have the possibility of meeting. In a tree (no cycles, single path between any two nodes), the forward and backward searches follow the same path and there is no savings. Bidirectional BFS shines on dense graphs with high branching factors, where the two expanding spheres meet in a large shared middle region.

When It Does Not Help

Unknown target state. Problems like "find the nearest exit in a maze" (where any boundary cell could be the exit) do not have a single known endpoint. You cannot start a backward search from an unknown set of goals. Multi-source BFS from all exits would be the right approach there.

Tree-structured search spaces. If there is only one path from start to goal, both searches explore the same nodes and you gain nothing.

Very small search spaces. If standard BFS already runs quickly, bidirectional BFS adds code complexity without meaningful speedup. The overhead of maintaining two frontiers, checking intersections, and swapping is only worthwhile when the search space is large.

Asymmetric branching. If the backward graph has a much higher branching factor than the forward graph (or vice versa), bidirectional BFS may not save as much as expected. The "expand the smaller frontier" heuristic mitigates this, but in extreme cases one-directional BFS with pruning might be simpler.

Complexity Analysis

Let $b$ be the branching factor and $d$ be the depth of the shortest path.

Standard BFS: explores $O(b^d)$ nodes. Time and space are both $O(b^d)$.

Bidirectional BFS: each direction explores roughly $d/2$ levels. The forward search explores $O(b^{d/2})$ nodes and the backward search explores $O(b^{d/2})$ nodes. Total nodes explored: $O(b^{d/2})$. Time and space are both $O(b^{d/2})$.

The ratio of improvement is $b^d / b^{d/2} = b^{d/2}$. For $b = 25$ (roughly the branching factor for 5-letter words) and $d = 10$, this is $25^5 \approx 10^7$, a ten-million-fold reduction.

For the Word Ladder problem specifically, where $L$ is the word length and $N$ is the dictionary size, generating neighbors takes $O(26L)$ per word. Standard BFS visits up to $O(N)$ words, giving $O(26LN)$ total time. Bidirectional BFS visits fewer words in practice but has the same worst-case bound of $O(26LN)$ since the dictionary size caps the exploration. The practical improvement comes from visiting far fewer words on average, not from a change in worst-case complexity relative to $N$.

For Open the Lock, the state space has $10^4$ states, each with 8 neighbors. Both standard and bidirectional BFS are $O(10^4 \cdot 8) = O(8 \times 10^4)$ in the worst case, but bidirectional BFS typically terminates much earlier because the two frontiers collide quickly in the densely connected state graph.

Recognizing this pattern

You're probably looking at bidirectional BFS when:

• You have a single explicit source and a single explicit target in a large state space
• The branching factor is moderate, so plain BFS from one side would blow up exponentially with depth
• The graph is undirected (or you can traverse both directions) and you can generate neighbors symmetrically from either end
• Problems involve transforming a string, a configuration, or a lock state into another via small steps

Common templates:

• Two-set BFS with swap: keep two frontiers, always expand the smaller one, check membership in the other for a meeting point. Example: Word Ladder.
• Pattern-neighbor generation: generate neighbors by mutating one position at a time and intersect with a dictionary. Example: Word Ladder II.
• State-space search with hashing: encode the state as a hashable string or tuple and run bidirectional BFS over the implicit graph. Example: Open the Lock.
• Minimum-step puzzle solve: apply bidirectional BFS to sliding puzzles or configuration games with a known target. Example: Sliding Puzzle.