Breadth First Search

Tree and Graph traversal are one of the important topics in computer science.
In fact many social networking companies are using graph based database (nosql db) specially Facebook, Twitter, Linkedin, etc.

Traversing is all about visiting the vertices in some systematic order.

There are two types of traversal:

• Depth First Search (DFS)
• Breadth First Search (BFS)

If you don't have memory constraint, DFS is a good choice, as BFS takes up a lot of space. So, choosing between these two depends on user's requirement.

Following are traversal methods for trees using DFS:

• preorder : visit each node before its children.
• postorder: visit each node after its children.
• inorder : visit left subtree, node, right subtree. (applicable for binary trees only)

When to use DFS :

• When you want to find the (strongly/)connected components of the graph to
• To Solve the maze or sudoku problems.

When to use BFS:

• When you want to test if a graph is bipartite or 
• To find the shortest path between two nodes or applications that require such tasks.

I found following video very easy to understand about BFS.

Following code is for the BFS

Above code consider the following tree as input and output is ABSCGDEFH