Posted

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

Complexity
Time complexity: O(n)
Space complexity: best: O(1), worst: O(n/2)=O(n)

Advantages:
* 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.

Disadvantages
* A BFS on a binary tree generally requires more memory than a DFS.