How to Use Breath Fast Search Pattern for Cracking Coding Interviews

How to Recognize which questions can be solved by BFS and get offers from top tech companies

BFS based questions are one of the most asked questions in any coding interviews.

Personally, I got questions which were a slight variation of BFS in the interviews of companies like Uber, Samsung, Amazon and many startups as well.

Let’s talk about Breadth-First Search on graphs. Many problems can be visualized as a graph-based problem. They can be solved using either Breadth-First Search or Depth First Search. What is Breadth-First Search in Graph? We will answer this question in great details here

Definition

Breadth-first search is a graph traversal algorithm in which we start traversing the graph from the source/root node and explore all the neighboring nodes before exploring any of their children. Once all the neighboring nodes are explored, we will then select one of their children and repeat the process until we have explored all the nodes. That is we go wide (hence breadth-first search) before we go deep.

For simplicity, let's try to understand the BFS in a binary tree. We first take the root node of the tree and print it. We also need to add the left and right children of that node in a queue…