Breadth First search is an effective search mechanism for Graphs and Tree Data structure. As the name suggest, this technique makes sure that all the nodes at same level/ breadth are checked before moving to deeper levels.

The above structure is hybrid of tree and graph (Still a tree as there are no cycles). Let us what it means to do a breadth first search here.

We will start with root node i.e. 10.

Move to level 2 and check nodes 18, 22, 5.

Check the next level- 7, 15, 12 and so on.

Here is algorithm to implement Breadth first search

1. Add root node R to queue- Q

2. Fetch next node N from Q

3 a. If the N.val is required val, return success

3 b. Else Find all Child/ Neighbour nodes which are not traversed already and add to Queue

4. If there are more nodes in Q, Repeat from 2.

5. If Q is empty, we know we have traversed all nodes, return failure as node not found

Read more here- http://en.wikipedia.org/wiki/Breadth-first_search

http://en.wikipedia.org/wiki/Breadth-first_search