Breath-First-Search on Trees
Breath-First-Search, commonly abbreviated as BFS, is a tree/graph traversal algorithm that visits all the nodes level by level and then left to right. There can be variations of going right to left but the core concept is to go level by level.
As the idea of the algorithm is simple enough to understand, this article will focus on implementing variations of BFS.
Implementation
Breath-First-Search is often implemented using a queue. It begins by adding a root node to the queue and then removing that node, adding its children, and then processing the node. Below is a representation in Java.
The issue with this implementation is that it doesn’t print the nodes in sets as level-by-level such as:
[8],
[3,10],
[1,6,14],
[4,7,13]To achieve this, we will need the help of a ‘size’ variable and a for-loop. Let us also focus on maintaining the queue such that it only contains the nodes for the current level. If we know how many nodes in the queue relate to the current level, we can remove that many nodes from the queue and process each of them such that what’s remaining in the queue is nodes for the next level. The level with [1,6,14] from the photo above has 3 nodes. In knowing that we would like to process 3 nodes from the queue and leave 3 nodes,[4,7,13], for the next iteration.
Below is code to achieve this level-by-level variation of BFS.
A common question is why we need to record the size of the queue beforehand and not use queue.size() instead. The issue with using queue.size() is that the size of the queue will be constantly changing as nodes are added and removed. Therefore, having a dynamic for loop will not be able to achieve the level-by-level variation.
Thank you for reading. I am writing these articles for my friends who are interested in coding algorithms and for people like you looking to learn more. Please give a clap and follow if you found this article helpful!
