Pseudo Code
procedure BFS(G, start_v) is
let Q be a queue
label start_v as discovered
Q.enqueue(start_v)
while Q is not empty do
v := Q.dequeue()
if v is the goal then
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered then
label w as discovered
w.parent := v
Q.enqueue(w)
The implementation of Breadth First Search uses queue and while loop comparing to its cousin of depth first search uses recursion, and remember this, I believe, can help you at least build the structure during your coding interview.
Implementation
Consider the most basic task:

To find all the paths from 0 to 6.
Notice the bidirectional arrow of 1 and 4, which means if we don’t track the visited node during search, the path would go backward.
A few points need to take notice here:
- Notice the queue contains 2 elements, current node and current path. Based on the problem you meet, it could be depth or other things.
- The
queue.pop(0)
ensures that we always consider the first element in the queue, which makes it breadth first. - If we hit a leave node with no children, then we continue to the next
if curr_node not in self.graph.keys():
continue
- The
if child not in curr_path
checks if we are going backward, which avoids to visit a node twice. - Makes sure to
curr_path.copy()
, otherwise paths of different children would be entangled.
Coding Questions
Let’s see how we can apply it flexibly.
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
3
/
9 20
/
15 7
return its minimum depth = 2. (This is a question from leetcode)
The major changes here is that our path is replaced by depth as the question required.
Now the question comes, what if we want the maximum depth? Go have a try.