More Testing Video Screencasts Tutorials and Courses on Coursinator.com
Reading Time: 1 minute
In Breadth-first search (BFS) you start with the root, move left to right across the second level, then move left to right across the third level, and so forth. Breadth-first search (BFS) is a method for exploring a tree or graph. In a BFS, you first explore all the nodes one step away, then all the nodes two steps away, etc.
A BFS uses additional memory because it is necessary to track the child nodes for all nodes on a given level while searching that level.
Remember to use Queue, and isVisited flag to avoid infinite loop
Time complexity: O(n)
Space complexity: best: O(1), worst: O(n/2)=O(n)
* A BFS will find the shortest path between the starting point and any other reachable node. A depth-first search will not necessarily find the shortest path.
* A BFS on a binary tree generally requires more memory than a DFS.