To ace your coding interview for a software engineering job, you’ll need to understand breadth-first search. It comes up frequently in coding interviews and is fundamental to many other algorithms too.
Let’s take a look at some typical breadth-first search questions.
5 typical breadth-first search interview questions
Given the root of a binary tree, return the average value of the nodes on each level in the form of an array.
You have an undirected, connected graph of n nodes labeled from 0 to n-1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge. Return the length of the shortest path that visits every node.
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e. from left to right, level by level).
Given an array of integers arr, you are initially positioned at the first index of the array. Return the minimum number of steps to reach the last index of the array.
Given a binary tree, find its minimum depth.
Below, we take a look at 44 breadth-first questions and provide you with links to high quality solutions to them.
This is an overview of what we’ll cover:
Easy breadth-first search interview questions
- Medium breadth-first search interview questions
- Hard breadth-first search interview questions
- Breadth-first search basics
- Breadth-first search cheat sheet
- How to prepare for a coding interview
Let's get started.
You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of breadth-first search.
As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.
If you get stuck, go ahead and look at the solution, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.
Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the “phone screen” stage, so you should be comfortable answering them without being able to write code or use a whiteboard.
Question 1: Maximum depth of binary tree
Question 2: Minimum depth of binary tree
Question 3: Maximum depth of N-ary tree
Question 4: Average of levels in a binary tree
Question 5: Cousins in binary tree
Question 6: Find if path exists in graph
Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.
Question 7: Binary tree level order traversal
Question 8: Binary tree zigzag level order traversal
Question 9: Binary tree level order traversal II
Question 10: Clone graph
Question 11: Populating next right pointers in each node II
Question 12: Binary tree right side view
- Text guide (Medium/Nerd For Tech)
- Video guide (NeetCode)
- Video guide (Kevin Naughton Jr.)
- Code example (zwangbo)
Question 13: Number of islands
- Text guide (Tutorial Horizon)
- Video guide (Michael Muinos)
- Video guide (Errichto)
- Code example (jianchao-li)
Question 14: Course schedule
Question 15: Course schedule II
Question 16: Perfect squares
Question 17: Coin change
Question 18: Minimum height trees
Question 19: Water and jug problem
Question 20: Evaluate division
Question 21: N-ary tree level order traversal
Question 22: Find bottom left tree value
Question 23: Find largest value in each tree row
Question 24: Minesweeper
Question 25: Coloring a border
Question 26: Minimum jumps to reach home
Question 27: Map of highest peak
Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.
Question 28: Word ladder
Question 29: Word ladder II
Question 30: Cut off trees for golf event
Question 31: Sliding puzzle
Question 32: Bus routes
Question 33: Shortest path visiting all nodes
Question 34: K-Similar strings
Question 35: Shortest path to get all keys
Question 36: Escape a large maze
Question 37: Minimum moves to move a box to their target location
Question 38: Minimum number of flips to convert binary matrix to zero matrix
Question 39: Shortest path in a grid with obstacles elimination
Question 40: Jump game IV
- Text guide (Study Notes)
- Video guide (Naresh Gupta)
- Video guide (Algorithms Made Easy)
- Code example (hiepit)
Question 41: Minimum cost to make at least one valid path in a grid
Question 42: Frog position after T seconds
Question 43: Last day where you can still cross
Question 44: Minimum cost to reach destination in time
In order to crack questions about breadth-first search, you’ll need to have a strong understanding of the algorithm, how it works, and when to use it.
4.1 What is breadth-first search?
We can categorize all data structures into two categories: those with a simple option for visiting each item, and those with multiple, complex options for visiting each item. Data structures like arrays, list, stacks, and queues fall in the first category – we can easily visit each node in an array by traversing over the array indices; following each link for a list; popping from a stack; and dequeuing from a queue. But for a tree or graph data structure, it is not so simple.
Breadth-first search (BFS) is one traversal method for trees and graphs in which all vertices on one layer are visited before visiting their children on the next layer – i.e. every node on layer i is visited before the nodes on layer i+1. In the following example, traversal starts at the root node a, moves to the nodes in the next layer (b and c), and finally visits the nodes in the last layer, giving us an output of abcdef.
4.1.1 Use cases for breadth-first search (Java, Python, C++)
This search type has many use cases, some of which are:
- Finding the quickest or shortest solution to a problem. For example, in the tree above, if we start at state a and have states c and d as goal nodes, then BFS will stop once c is found. This is the optimal solution, as it is one move away from a while d is two moves away
- Implementing a crawler (like a web scraper) that stops once an arbitrary depth has been reached
- Detecting cycles in graphs
- Establishing whether a graph is connected (any node can be reached from any other) or disconnected (there are "islands" that cannot be reached from other parts of the graph)
- Checking if people in a social network are connected within k degrees of separation
BFS is also used in other algorithms, such as minimum spanning trees, Dijkstra’s shortest path algorithm, the Ford-Fulkerson algorithm, and Cuthill-McKee’s algorithm.
4.1.2 Example implementation
Let’s consider a BFS implementation for searching a tree data structure. At a high level, we need to keep track of the next layer of nodes to visit. This is done by pushing the current node’s children to a queue. In other words, child nodes on each level are visited after all parent nodes have been visited.
This tree algorithm will not work for graphs, since graph vertices can have more than one edge pointing to them. Take a look at the following three graphs.
In the first graph, the algorithm visits a, followed by its children, b and c. On visiting b and c, d will be pushed to the queue, resulting in d being visited twice. In the second graph, the algorithm will visit abc in an infinite cycle. In the last undirected graph, ab will be visited repeatedly.
The solution is to keep track of the vertices as they are visited. Here is a revised implementation for graphs that introduces the visited set:
This algorithm solves the previous three issues. In the first graph, expanding c won’t push d, since d is already in the visited set. In the second graph, expanding c won’t push a, since a is already in the visited set. Similarly in the third graph, the algorithm will not push a to the queue on visiting b, as a will be in the visited set.
A final case to consider is a disconnected graph, like the one below, in which all vertices need to be visited.
If our algorithm begins its search on the e vertex of the right subgraph, it will push f to the queue and stop. The left subgraph will not be visited. Starting with any of the vertices on the left subgraph would have the same result: the algorithm would not visit any of the vertices on the right.
We can solve this with the following revision:
Here we start the algorithm for every possible vertex in the graph. A loop is added to kickoff the algorithm for every vertex.
4.1.3 How breadth-first search compares to other algorithms
One alternative to BFS is depth-first search, but BFS is complete. This means that if the search space is infinite, then BFS will find the solution since BFS searches each layer at a time. In an infinite space, depth-first search can get trapped and will never find the solution, but in many cases DFS can find the solution faster if it exists in one of the paths explored first.
An adaptation of depth-first search called iterative deepening search (IDS) can be seen as a hybrid between BFS and depth-first search. IDS provides the completeness of BFS, with the advantages of depth-first search.
BFS assumes each edge of a vertex has an equal cost (an implicit cost of 1), but this might not always be the case. Consider distances between cities, for example. Uniform-cost search is an algorithm that uses a priority queue to find the next node to expand.
You can download the cheat sheet here.
5.1 Related algorithms and techniques
5.2 Cheat sheet explained
The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.
The cheat sheet is broken into time complexity and space complexity (the processing time and memory requirements for breadth-first search). Breadth-first search is related to several data structures, which are also included in the cheat sheet.
For more information about time and space requirements of different algorithms, read our complete guide to big-O notation and complexity analysis.
5.2.1 Time complexity
The tree implementation of BFS visits each node in the tree for a complexity of O(n). A stop condition can stop the search earlier and will, on average, visit half the nodes. So the worst and average case will be O(n).
The graph implementation of BFS visits each vertex and edge for a complexity of O(V + E). Again, a stop condition might stop the search early, visiting half the vertices on average. So the worst and average case will be O(V + E).
5.2.2 Space complexity
For the tree implementation of BFS, the queue size will be bounded by the number of leaf nodes. On average, this will be half of all the nodes, but it could be all the nodes except the root, for example, for a tree with one root node and all other nodes being direct children of the root. In both cases BFS has a space complexity of O(n).
For the graph implementation of BFS, every vertex will be in the visited set at the end of the search, giving a space complexity of O(V).
5.2.3 Related algorithms and data structures: Dijkstra’s algorithm
Dijkstra’s shortest path algorithm is an adaptation of BFS, in which each edge has a weight. Rather than taking the oldest item of the queue (FIFO), it uses a priority queue to dequeue the node with the shortest distance from those nodes to visit next. When this node is expanded, its weight is added to the distance to its children before each child is enqueued. This can then be used to find the shortest route between two cities on a map, for example. The algorithm will stop when the destination vertex (the destination city, in our example) is dequeued.
Like a graph BFS, each vertex and edge will be visited in the worst case, and only half in the average case. Dequeuing from a priority queue is constant time. Combined, these give both cases a time complexity of O(V + E). For space complexity, all the vertices might end up in the visited set resulting in O(V).
When all the edges in the graph have an equal weight, Dijkstra’s shortest path will reduce to the first graph implementation for BFS.
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only breadth-first search but also the rest of the relevant algorithms and data structures. You’ll also want to start working through lots of coding problems.
Check out the guides below for lists of questions organized by difficulty level, links to high-quality answers, and cheat sheets.
- Depth-first search
- Binary search
- Dynamic programming
- Greedy algorithm
- Divide and conquer
Data structure guides
- Linked lists
- Stacks and Queues
- Coding interview examples (with solutions)
To get used to an interview situation, where you’ll have to code on a whiteboard, we recommend solving the problems in the guides above on a piece of paper or google doc.
6.2 Practice with others
However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.
That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.
Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.