Breadth First Search Theory

In Breadth First Search (BFS), the key is that it is a level-based, or row-based movement. At each level or row, the nodes of a tree are visited/traversed horizontally from left to right or right to left.

The horizontal direction chosen will depend on the problem statement. For instance, a problem that is looking for the sum of all nodes on the right-hand side may necessitate right-to-left traversal. This would allow you to just grab the first node, and immediately move on to the next level, without wasting cycles visiting the others.

In this lesson, we will see how to perform breadth first search from left to right.

Let's take an example. If you look at the previous tree again, the tree has 4 levels:

1. At level 1, the tree has the root node A.
2. At level 2, it has two nodes B and C.
3. Similarly, level 3 contains nodes D, E, F, G.
4. Finally, at level 4, nodes H, I, J are present. If the tree is searched via the breadth first search technique, the nodes would be traversed in the following order:

1A-B-C-D-E-F-G-H