Mark As Completed Discussion

Let's discuss implementation, or how we'd actually write the program to conduct BFS. Before jumping into the code, we'll review the steps in plain English. The steps to implement the breadth first search technique to traverse the above tree are as follows:

  1. Add the node at the root to a queue. For instance, in the above example, the node A will be added to the queue.
  2. Pop an item from the queue and print/process it.
  3. This is important-- add all the children of the node popped in step two to the queue. At this point in time, the queue will contain the children of node A:

At this point, we've completed our processing of level 1. We would then repeat steps 2 and 3 for B and C of level 2, and continue until the queue is empty.

SNIPPET
1// Step 1
2queue = [A]
3// Step 2
4queue = [B, C]
5// And so on...

Here's a visual of the program being run:

Implementing BFS