Breadth-First Traversal(or Search) of a Tree

Basically their are two ways or techniques to traverse a tree. The first method is caleed Breadth First Search or BFS and the second approach is known as Depth First Search or DFS. In this article we are goinmg to discuss the BFS method to traverse a tree.  

As we know that tree is also a graph but unlike trees, graph may contain cycles. So to traverse a binary(a node can have at most two child nodes i.e. 0,1,2 nodes possible) the idea is to use a Queue Data Structure.

Points To Remember:

1. In BFS nodes at the same level are visited first before moving on to the next level.
2. The level of the tree is calculated from root node. The level of the root is 0 and it's child is 1 and so on. So in BFS start with the root node.
3. Next we will check if their are other nodes to visit in the current level. If other node exist in the same level to visit then visit them.
4. Once all the nodes of same level visited then we will move to the next level.
5. We will repeat the process till every node is visited in the tree.

Binary Tree

Let assume we have this binary tree ti traverse it's every node. So we will start with the root node that is 'A' and then it's all child nodes in the next level i.e. in level 1, B and C. We will repeat this process till every node is visited or traversed.

Algorthim:

1. First check the base case that root node is not null otherwise return.
2. Create an arrayList to store the processed nodes so that we can print the nodes from the arrayList
3. Create a queue of NodeOfATree objct.
4. Store the root node into the queue to process.
5. Dequeue the node from the queue which is at the very front
6. Add it into the Arrylist to print.
7. Now if the node that we just dequeued has a left subtree than add it into the queue.
8. And if it has a right subtree than add it into the queue.
9. Perform the step 5 to 8 until queue becomes empty.
10. Print the nodes that are their in the array list, that we just created in step no 2.

So first let's construct the binary tree. We will create a generic class named NodeOfATree whose data type will be generic so that the nodes of the tree can be of any data type, be it int, char, object etc. And our main driver class will be named as BFS inside this we will call our method breadthFirstSearch which will accepts the root of the tree to traverse.

Output:

A - > B - > C - > 

A - > B - > C - > D - > E - > 

A - > B - > C - > D - > E - > F - > H - > 

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