Breadth-first search (BFS) Interview Questions and Practice Problems

Coding Freak
Sep 1, 2018 · 2 min read

A Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.

Above image shows order in which the nodes are expanded in BFS. Here’re the list of commonly asked interview questions that can be solved using BFS –

  1. Breadth First Search (BFS) | Iterative & Recursive Implementation
  2. Determine if given graph is Bipartite Graph or not
  3. Minimum number of throws required to win Snake and Ladder game
  4. Check if an undirected graph contains cycle or not
  5. Chess Knight Problem | Find Shortest path from source to destination
  6. Shortest path in a Maze | Lee algorithm
  7. Find shortest safe route in a field with sensors present
  8. Flood Fill Algorithm
  9. Count the number of islands
  10. Find Shortest path from source to destination in a matrix that satisfies given constraints
  11. Least Cost Path in Weighted Digraph using BFS
  12. Find maximum cost path in graph from given source to destination
  13. Least cost path in given digraph from given source to destination having exactly m edges
  14. Traverse the given directory using BFS and DFS in Java
  15. Find shortest distance of every cell from landmine in a Maze
  16. Check if given binary tree is complete binary tree or not
  17. Level Order Traversal of Binary Tree
  18. Total number of paths in given digraph from given source to destination having exactly m edges

Thank you.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade