Bidirectional BFS explained: how it works and when to use it

In this article

1. Before you start
2. Why interviewers ask this
3. Bidirectional BFS from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Bidirectional BFS is one of the graph patterns that come up in coding interviews. If graph search is new, read it with a pencil in hand.

Why interviewers ask this

A shortest-path question on a very large graph is where a plain BFS runs out of time or memory, so bidirectional BFS is a common upgrade. Community solutions to Word Ladder, such as AlgoMonster's, use bidirectional BFS to reduce the search space.

The question separates three kinds of answer. A weak answer says "run BFS from both ends" and stops there. A strong answer names the two frontiers, the distance maps, the meeting test and the final sum, and says what the technique needs from the graph. A Staff-level answer also says what it does not change: the worst-case bound stays the same, the saving is in the exponent, and the stopping rule differs once edges carry weights. Interviewers listen for whether you know when the technique applies, not only how to code it.

Bidirectional BFS from first principles

Bidirectional BFS

Bidirectional BFS is a shortest-path search that runs two breadth-first searches in turn, one forward from the start node and one backward from the goal node, and stops when a node found by one search is already known to the other, which gives the path length.

Frontier

A frontier is the set of nodes that one search has discovered in its newest layer but has not yet expanded, so it is the edge of the region that search has covered and the list of nodes it will expand next.

In plain words

Picture a tunnel dug through a mountain. One crew digs from the east, one from the west. Each crew digs only half the length, and they stop when the tunnels join.

The analogy breaks in one place. Tunnel crews dig in a known direction. A search has no direction, so each side spreads in every direction at once, layer by layer.

In one precise sentence: bidirectional BFS grows a ball of visited nodes around the start and another around the goal, and ends when the two balls touch. Two small balls hold fewer nodes than one big ball, which is where the saving comes from. Bidirectional search was already in use for two-node shortest paths when Pohl (1971) analyzed it and extended it to heuristic search; the Wikipedia summary describes the idea of one search forward from the initial state and one backward from the goal.

Step 1: Keep two frontiers and two distance maps

Bidirectional BFS starts with two frontiers and two distance maps, one pair at the start and one at the goal. The forward frontier holds the start node, and the forward map says the start is zero edges from itself. The backward frontier holds the goal, and the backward map says the goal is zero edges from itself.

A distance map is a hash map from a node to its distance from its own origin. It does two jobs: it records the distance, and a lookup in it answers "has this side seen this node?", which makes it the visited set. The Cornell lecture likewise keeps distances in a map that can be implemented as a hash table. Lookups cost constant time on average, so the checks stay cheap.

Input: the start and the goal. Output: two one-node frontiers and two one-entry maps. If the start equals the goal, the answer is zero and no search is needed. You now know the whole state of the algorithm; the next step changes it.

Step 2: Expand the smaller frontier one whole layer

Expand the smaller frontier one whole layer at a time. To expand a node on the forward side, list its neighbors. On the backward side, list its predecessors. A predecessor of a node X is a node that has an edge leading to X. On an undirected graph the predecessors are the neighbors. On a directed graph you need a reverse adjacency list, a map from each node to the nodes pointing at it, which you can build with a defaultdict in Python.

Expanding the smaller side is a heuristic, not a requirement for correctness. Community write-ups such as AlgoMonster's Word Ladder solution use it because the work of a layer grows with its size, so growing the small side first keeps the cost low. Input: one frontier. Output: its next layer, with each new node added to that side's map at distance one more than its parent. The layer is processed as a whole; Step 3 explains why that matters.

Step 3: Stop when a generated node is already on the other side

The search stops when a generated node is already on the other side. While expanding a node u, take each node v it leads to. If v is in the other side's map, the two searches have met, and you stop. Otherwise record v's distance and queue it.

Why is the first meeting the shortest path on an unweighted graph? Before a layer is expanded, the two maps share no node. Suppose the forward side has reached depth k and the backward side depth j. If a path of length at most k plus j existed, one node of that path would lie within k of the start and within j of the goal, so it would sit in both maps.

It does not, so every path is at least k plus j plus 1 long. The meeting node closes a path of at most that length, so the first meeting is a shortest path. A check on 1,000 random start-goal pairs on undirected graphs found no disagreement with plain BFS.¹

With weighted edges the rule changes, as the trade-offs section shows.

Step 4: Add the two distances to get the path length

The path length is the forward distance plus one plus the backward distance. When u on the forward side leads to v already on the backward side, the path runs from the start to u, across the edge from u to v, and from v to the goal. The distances are the forward distance of u, one edge, and the backward distance of v.

Many problems count nodes or words, not edges, so check what the answer should be. Word Ladder counts words, so its answer is the edge count plus one. Input: the meeting edge and the two maps. Output: one number. Here is the whole algorithm in Python, for a graph given as two functions:

def shortest_path_length(start, goal, neighbors, predecessors):
    if start == goal:
        return 0
    dist_f, dist_b = {start: 0}, {goal: 0}
    front_f, front_b = [start], [goal]
    while front_f and front_b:
        forward = len(front_f) <= len(front_b)
        if forward:
            front, mine, other, step = front_f, dist_f, dist_b, neighbors
        else:
            front, mine, other, step = front_b, dist_b, dist_f, predecessors
        next_front = []
        for u in front:
            for v in step(u):
                if v in other:
                    return mine[u] + 1 + other[v]
                if v not in mine:
                    mine[v] = mine[u] + 1
                    next_front.append(v)
        if forward:
            front_f = next_front
        else:
            front_b = next_front
    return -1  # no path

The loop ends with -1 when one side runs out of nodes, which means the goal cannot be reached. Each line maps to a step above.

1 · Two frontiers2 · Expand smaller3 · Meeting test4 · Add distancesReplay

Step-by-step description

1. One frontier and map at the start, one at the goal.
2. Expand the smaller side by one whole layer.
3. Stop when a new node is on the other side.
4. Forward plus one plus backward.

• Two frontiers and two distance maps start at the start and the goal.
• Expand the smaller frontier one whole layer at a time.
• The search stops when a generated node is already on the other side.
• The path length is the forward distance plus one plus the backward distance.

Worked example

Word Ladder asks for the shortest chain from a begin word to an end word where each step changes one letter and each new word is in a list. The LeetCode statement gives begin word "hit", end word "cog" and the list hot, dot, dog, lot, log, cog, with answer 5. The graph is implicit: an implicit graph is a graph never stored as a list of edges, because the neighbors of a node are computed on demand, here by changing one letter and checking the word list.

Round 3 goes backward because the forward frontier holds two words and the backward frontier one. In round 4 the forward distance of dot is 2 edges and the backward distance of dog is 1, so the path has 2 plus 1 plus 1 equals 4 edges, and 5 words.¹ If the end word is missing from the list, as in the second LeetCode example, the answer is 0. Six words is too small to show a real saving, so the next table uses the simple model.

The branching factor is the number of new nodes each node leads to, and here it is 10. The Wikipedia model says each search costs about $O(b^{d/2})$ against $O(b^d)$ for one search. The table counts the deepest layer only: a single search visits 10 to the power d nodes and a pair visits 2 times 10 to the power d/2. The saving ratio is 5 at distance 2 and 5,000 at distance 8.¹

Text description of the diagram

• The saving ratio is 5 at distance 2.
• The saving ratio is 5,000 at distance 8.

Generating neighbors is cheap in Word Ladder. A word of up to ten letters has 26 times 10 equals 260 one-letter substitutions, of which 250 differ from the word, and each is one hash-set lookup. Scanning a list of up to 5,000 words instead would compare 20 times as many candidates.¹

Trade-offs and edge cases

Bidirectional BFS trades requirements for fewer node visits. Plain BFS needs only a start node, while bidirectional BFS needs a known goal and a way to list predecessors. Both searches have the same worst-case bound, $O(V+E)$, the cost Sedgewick and Wayne give for BFS, which they say takes time proportional to V plus E in the worst case: V counts nodes and E counts edges. The saving is in the exponent of the number of nodes explored when branching is large.

Text description of the diagram

• Plain BFS needs only a start node, while bidirectional BFS needs a known goal and a way to list predecessors.
• Both searches have the same worst-case bound, O(V+E).

Edge cases to name in an interview:

• Slow-growing graphs. On an open grid the explored region grows with the square of the distance, not exponentially. For a goal 10 steps away, a plain search covers up to 221 cells and two searches of radius 5 cover 122, a gain under two times.¹
• Directed graphs. Predecessors need a reverse adjacency list. The edges need not be symmetric; the backward side only needs to list which nodes lead to X. If directed graphs are new, see how to detect a cycle in a directed graph.
• Weighted edges. BFS counts edges, so weights call for Dijkstra, a shortest-path algorithm that always expands the cheapest unfinished node first. Bidirectional Dijkstra needs its own termination conditions; the first-meeting rule above does not carry over.
• Memory. Both frontiers live in memory, and each can still be large.
• Heuristic search. Heuristic search steers the search with an estimate of the distance left to the goal. Pohl's 1971 paper also covered the heuristic version; it is a separate topic.

A related idea is finding where two paths meet, as in lowest common ancestor. Another queue-driven graph method is topological sort.

How to answer it in an interview

The spoken structure: define it, say how it expands and stops, give the length formula, then name the saving and the requirements.

Common mistakes

• "I run two full BFS searches and join them." (wrong) Each side stops near the middle depth; running both to the end loses the saving. (right) "Each side goes about halfway, and I stop at the first meeting."
• "It only works on undirected graphs." (wrong) You only need to list the predecessors of a node. (right) "On a directed graph I keep a reverse adjacency list."
• "Bidirectional BFS has a better worst-case bound." (wrong) The bound stays $O(V+E)$. (right) "It explores far fewer nodes when branching is large, but the worst case is unchanged."
• "The answer is forward distance plus backward distance." (wrong) That misses the edge joining the two sides. (right) "Forward plus one plus backward, then adjust for counting words instead of edges."
• "I stop at the first meeting on a weighted graph." (wrong) Weighted graphs need special termination conditions. (right) "For weights I use bidirectional Dijkstra with its stopping rule."

Follow-up questions

Is bidirectional BFS always faster than BFS?

No. It helps when the branching factor is large and the goal and predecessors are known. On slow-growing graphs such as a grid the gain is under two times, and the worst-case bound does not change.

How does bidirectional BFS work on a directed graph?

The forward side follows edges as given and the backward side follows them in reverse, so you need a reverse adjacency list or a function that lists predecessors. The edges themselves need not be symmetric.

What is the time complexity of bidirectional BFS?

In the simple tree model each side costs about $O(b^{d/2})$ against $O(b^d)$ for one search. In the worst case on a general graph the bound is still $O(V+E)$, as for BFS.

How do you solve Word Ladder with bidirectional BFS?

Start from the begin word and the end word, generate neighbors by changing one letter and checking a hash set of the word list, expand the smaller side by a layer, and stop when a word is already on the other side. Return the edge count plus one, or 0 if the end word is not in the list.

How do you return the path itself, not just its length?

Store a parent map on each side. When u on the forward side leads to v on the backward side, build start to u from the forward parents, add the edge u to v, then build v to goal from the backward parents. Dictionary lookups for the parents are covered in Python interview questions. Word Ladder II asks for all shortest paths, so each node keeps a list of parents and the search finishes the layer.

Does bidirectional search work with weighted edges?

Yes, in the form of bidirectional Dijkstra, but the stopping rule is different from the unweighted case, and a wrong rule can return a path that is not the shortest.

Sources

1. Pohl, I. (1971). Bi-directional Search. Machine Intelligence 6, pp. 127-140 — Edinburgh University Press, 1 Jan 1971
2. Bidirectional search — Wikipedia, 26 Oct 2026
3. CS 312 Lecture 26: Graph Search Algorithms — Cornell University, 1 Jan 2005
4. Algorithms, 4th edition, section 4.1: Undirected Graphs (Sedgewick and Wayne) — Princeton University, 26 Oct 2026
5. TimeComplexity (Python wiki) — Python Software Foundation, 26 Oct 2026
6. 127. Word Ladder — LeetCode, 26 Oct 2026
7. Word Ladder solutions (LeetCode 127) — AlgoMonster, 26 Oct 2026