Breadth First Search (BFS) – Interview Questions & Practice Problems

Breadth-first search (BFS) algorithm is often used for traversing/searching a tree/graph data structure. It starts at the root (in the case of a tree) or some arbitrary node (in the case of a graph) and explores all its neighbors, followed by the next-level neighbors, and so on.

Consider the following tree which marks the order in which the nodes will be discovered in BFS:

 
In this post, we have listed out some of the commonly asked interview questions that can be solved using the BFS algorithm:

1. Breadth-First Search (BFS)
2. Transitive closure of a graph
3. Check if a graph is strongly connected or not
4. Find root vertex of a graph
5. Efficiently print all nodes between two given levels in a binary tree
6. Chess Knight Problem | Find the shortest path from source to destination
7. Shortest path in a maze – Lee Algorithm
8. Find the shortest safe route in a field with sensors present
9. Flood Fill Algorithm
10. Count number of islands
11. Find the shortest path from source to destination in a matrix that satisfies given constraints
12. Calculate the height of a binary tree
13. Delete a binary tree
14. Level order traversal of a binary tree
15. Spiral order traversal of a binary tree
16. Reverse level order traversal of a binary tree
17. Print all nodes of a perfect binary tree in a specific order
18. Print left view of a binary tree
19. Find the next node at the same level as the given node in a binary tree
20. Check if a binary tree is a complete binary tree or not
21. Print diagonal traversal of a binary tree
22. Print corner nodes of every level in a binary tree
23. Invert Binary Tree
24. Find minimum passes required to convert all negative values in a matrix
25. Convert a binary tree into a doubly-linked list in spiral order
26. Check if a binary tree is a min-heap or not
27. Invert alternate levels of a perfect binary tree
28. Snake and Ladder Problem
29. Find the shortest distance of every cell from a landmine inside a maze
30. Check if an undirected graph contains a cycle or not
31. Find maximum cost path in a graph from a given source to a given destination
32. Total paths in a digraph from a given source to a destination having exactly m edges
33. Least cost path in a digraph from a given source to a destination having exactly m edges
34. Traverse a given directory using BFS and DFS in Java
35. Perform vertical traversal of a binary tree
36. Compute the maximum number of nodes at any level in a binary tree
37. Print right view of a binary tree
38. Find the minimum depth of a binary tree
39. Depth-First Search (DFS) vs Breadth-First Search (BFS)
40. Bipartite Graph
41. Compute the least cost path in a weighted digraph using BFS
42. Find the path between given vertices in a directed graph
43. Construct a directed graph from an undirected graph that satisfies given constraints
44. Print nodes of a binary tree in vertical order