To ace your coding interview for a software engineering job, you’ll need to understand breadthfirst search. It comes up frequently in coding interviews and is fundamental to many other algorithms too.
Let’s take a look at some typical breadthfirst search questions.
5 typical breadthfirst 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 n1. 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 breadthfirst questions and provide you with links to high quality solutions to them.
This is an overview of what we’ll cover:

Easy breadthfirst search interview questions
 Medium breadthfirst search interview questions
 Hard breadthfirst search interview questions
 Breadthfirst search basics
 Breadthfirst search cheat sheet
 How to prepare for a coding interview
Let's get started.
1. Easy breadthfirst search interview questions
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 breadthfirst 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
 Text guide (Aaronice)
 Video guide (NeetCode)
 Code example (makuiyu)
Question 2: Minimum depth of binary tree
 Text guide (After Academy)
 Video guide (Terrible Whiteboard)
 Code example (simkieu)
Question 3: Maximum depth of Nary tree
 Text guide (Medium/Annamariya Tharayil)
 Video guide (Nick White)
 Code example (TKroos)
Question 4: Average of levels in a binary tree
 Text guide (Dev.to/seanpgallivan)
 Video guide (Michael Muinos)
 Code example (earlme)
Question 5: Cousins in binary tree
 Text guide (Medium/Yinfang)
 Video guide (Ren Zhang)
 Code example (Frimish)
Question 6: Find if path exists in graph
 Text guide (Open Genus)
 Video guide (CodeClips)
 Code example (aparna_g)
2. Medium breadthfirst search interview questions
Here are some moderatelevel 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
 Text guide (Educative)
 Video guide (Kevin Naughton Jr.)
 Video guide (Nick White)
 Code example (SOY)
Question 8: Binary tree zigzag level order traversal
 Text guide (zhenyu0519)
 Video guide (Michael Vandi)
 Code example (fangkunjnsy)
Question 9: Binary tree level order traversal II
 Text guide (Medium/Navneet Ojha)
 Video guide (Terrible Whiteboard)
 Code example (OldCodingFarmer)
Question 10: Clone graph
 Text guide (CodeProject)
 Video guide (Back to Back SWE)
 Code example (jianchaoli)
Question 11: Populating next right pointers in each node II
 Text guide (Medium/Nerd For Tech)
 Video guide (babybear4812)
 Code example (flashstone)
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 (jianchaoli)
Question 14: Course schedule
 Text guide (Yu Coding)
 Video guide (Nideesh Terapalli)
 Code example (jianchaoli)
Question 15: Course schedule II
 Text guide (Yu Coding)
 Video guide (Shiran Afergan)
 Code example (lx223)
Question 16: Perfect squares
 Text guide (YaokaiYang)
 Video guide (Coding Beats)
 Code example (zhukov)
Question 17: Coin change
 Text guide (GeekForGeeks)
 Code example (emmarong)
Question 18: Minimum height trees
 Text guide (Kennyzhuang)
 Video guide (Algoithms Made Easy)
 Code example (NoobAllStar)
Question 19: Water and jug problem
 Text guide (Coding Ninjas)
 Video guide (happygirlzt)
 Code example (leetcodedavy)
Question 20: Evaluate division
 Text guide (ProgrammerAll)
 Video guide (Happy Coding)
 Code example (mlaw0)
Question 21: Nary tree level order traversal
 Text guide (Tutorialspoint)
 Video guide (Coding Decoded)
 Code example (cenkay)
Question 22: Find bottom left tree value
 Text guide (Know Thyself)
 Video guide (Genetic Coders)
 Code example (StefanPochmann)
Question 23: Find largest value in each tree row
 Text guide (Code Destine)
 Video guide (Naresh Gupta)
 Code example (StefanPochmann)
Question 24: Minesweeper
 Text guide (Fatal Errors)
 Video guide (babybear4812)
 Code example (shawngao)
Question 25: Coloring a border
 Text guide (Massive algorithms)
 Video guide (Nideesh Terapalli)
 Code example (lee215)
Question 26: Minimum jumps to reach home
 Text guide (Medium/Ryan)
 Video guide (Happy Coding)
 Code example (gucciGang)
Question 27: Map of highest peak
 Text guide (Krammerliu)
 Video guide (Lead Coding by FRAZ)
 Code example (hiepit)
3. Hard breadthfirst search interview questions
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
 Text guide (Medium/Nathan Brickett)
 Video guide (Nick White)
 Code example (jianchaoli)
Question 29: Word ladder II
 Text guide (medium/spylogsster)
 Video guide (TECH DOSE)
 Code example (antdavid)
Question 30: Cut off trees for golf event
 Text guide (Zirui)
 Video guide (Shivam Patel)
 Code example (shawngao)
Question 31: Sliding puzzle
 Text guide (Medium/Feng Wang)
 Video guide (code_report)
 Code example (ShinozakiAi)
Question 32: Bus routes
 Text guide (LeetCode)
 Video guide (code_report)
 Code example (lee215)
Question 33: Shortest path visiting all nodes
 Text guide (Seanforfun)
 Video guide (Salita Programming)
 Code example (simonzhu91)
Question 34: KSimilar strings
 Text guide (Jolyon)
 Video guide (Shivam Patel)
 Code example (GraceMeng)
Question 35: Shortest path to get all keys
 Text guide (Tutorialspoint)
 Video guide (happygirlzt)
 Code example (wangzi6147)
Question 36: Escape a large maze
 Text guide (lee215)
 Video guide (Shivam Patel)
 Code example (dennyzhang)
Question 37: Minimum moves to move a box to their target location
 Text guide (Know Thyself)
 Video guide (Errichto)
 Code example (zypher27)
Question 38: Minimum number of flips to convert binary matrix to zero matrix
 Text guide (Tutorialspoint)
 Video guide (Algorithms for Big Bucks)
 Code example (rock)
Question 39: Shortest path in a grid with obstacles elimination
 Text guide (Tutorialspoint)
 Video guide (Knapsak)
 Code example (laser)
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
 Text guide (lee215)
 Video guide (code Explainer)
 Code example (astrowu)
Question 42: Frog position after T seconds
 Text guide (Sohojeprogramming)
 Video guide (Shivam Patel)
 Code example (hiepit)
Question 43: Last day where you can still cross
 Text guide (walkccc)
 Video guide (Coders Camp)
 Code example (hiepit)
Question 44: Minimum cost to reach destination in time
 Text guide (Krammer Liu)
 Video guide (Happy Coding)
 Code example (Invulnerable)
4. Breadthfirst search basics
In order to crack questions about breadthfirst search, you’ll need to have a strong understanding of the algorithm, how it works, and when to use it.
4.1 What is breadthfirst 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.
Breadthfirst 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 breadthfirst 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 FordFulkerson algorithm, and CuthillMcKee’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 breadthfirst search compares to other algorithms
One alternative to BFS is depthfirst 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, depthfirst 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 depthfirst search called iterative deepening search (IDS) can be seen as a hybrid between BFS and depthfirst search. IDS provides the completeness of BFS, with the advantages of depthfirst 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. Uniformcost search is an algorithm that uses a priority queue to find the next node to expand.
5. Breadthfirst search cheat sheet
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 breadthfirst search). Breadthfirst 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 bigO 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.
6. How to prepare for a coding interview
6.1 Practice on your own
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only breadthfirst 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 highquality answers, and cheat sheets.
Algorithm guides
 Depthfirst search
 Binary search
 Sorting
 Dynamic programming
 Greedy algorithm
 Backtracking
 Divide and conquer
Data structure guides
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 exinterviewers 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 1on1 with exinterviewers from leading tech companies. Learn more and start scheduling sessions today.
Any questions about breadthfirst search?
If you have any questions about breadthfirst search or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!