Breadth First Search(BFS)
In this blog post, I will be giving a brief description about another pattern that is very important for technical interview. The pattern is called Breadth First Search(BFS).
This pattern is used for traversing or searching tree or graph data structure. It uses a queue to keep track of all the nodes of a level before jumping onto the next level. This pattern is very useful to solve the problem that involves traversal of a tree in level-by-level order.
The steps involved for the above diagram in BFS are as follows;
-At first, we allocate node ‘a’ as a starting root node and insert it into the queue.
-Then ‘a’ node is extracted and the child nodes of ‘a’ which are ‘b’ and ‘c’ put into the queue.
-Then we print ‘a’.
-Then the first node in the queue is extracted again similarly.
-Next, the child of ‘b’ which are ‘d’ and ‘e’ are inserted into the queue and extracted for printing.
-Then we recursively repeat the steps until the queue is empty.
-We cannot repeat the steps for already visited nodes.
How to identify if the problem requires this pattern?
The problem will mainly involve traversing of tree in level-to-level fashion.
References:
