Breadth First Search (BFS)

BFS is naturally associated with queue. Visiting a node would be offering it to the queue. And polling it out of the queue to do level search.

Types of Questions

• BFS on Binary Tree
  • Level Order Traversal (separated by level, so an extra for loop on the size)
  • Store all nodes in the level order. The queue works as an ArrayList
• BFS on Graph
  • Traverse graph (clone graph, search graph nodes), need to check cycle
• • Topological Sort (Course Schedule, Alien Dictionary, etc)
• BFS on 2D Array
  • Put an index in the queue the keep searching (number of islands, N-queen)

Time Complexity

Wikipedia - BFS