To ace your coding interview for a software engineering job, you’ll need to understand depth-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 depth-first search questions.
5 typical depth-first search interview questions
-
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
-
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1. Return the size of the largest island in the grid after applying this operation.
-
Given the root of a binary tree, return the inorder traversal of its nodes' values.
-
Given an m x n 2D binary grid which represents a map of "1"s (land) and "0"s (water), return the number of islands.
-
Given an m x n integers matrix, return the length of the longest increasing path in the matrix.
Below, we take a look at 50 more depth-first search questions and provide you with links to high quality solutions to them.
This is an overview of what we’ll cover:
-
Easy depth-first search interview questions
- Medium depth-first search interview questions
- Hard depth-first search interview questions
- How to prepare for a coding interview
Let's get started.
1. Easy depth-first 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 depth-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.
1.1 Binary tree inorder traversal
- Text guide (Dev.to/javinpaul)
- Video guide (DEEPTI TALESRA)
- Code example (OldCodingFarmer)
1.2 Same tree
- Text guide (Fatal Errors)
- Text guide (LeetCode)
- Video guide (NeetCode)
- Code example (OldCodingFarmer)
1.3 Symmetric tree
- Text guide (Baeldung)
- Text guide (Medium/Hary Krishnan)
- Video guide (Back To Back SWE)
- Code example (lvlolitte)
1.4 Maximum depth of binary tree
- Text guide (Medium/The Startup)
- Video guide (NeetCode)
- Code example (makuiyu)
1.5 Balanced binary tree
- Text guide (Techie Delight)
- Video guide (Back To Back SWE)
- Code example (benlong)
1.6 Path sum
- Text guide (After Academy)
- Video guide (Kevin Naughton Jr.)
- Code example (OldCodingFarmer)
1.7 Binary tree preorder traversal
- Text guide (Techie Delight)
- Video guide (DEEPTI TALESRA)
- Code example (OldCodingFarmer)
1.8 Binary tree postorder traversal
- Text guide (Techie Delight)
- Video guide (Kevin Naughton Jr.)
- Video guide (Tushar Roy)
- Code example (yavinci)
1.9 Invert binary tree
- Text guide (After Academy)
- Video guide (NeetCode)
- Code example (jmnarloch)
1.10 Lowest common ancestor of a binary search tree
- Text guide (Aaronice)
- Video guide (NeetCode)
- Video guide (Tushar Roy)
- Code example (jingzhetian)
- Code example (Hacker Rank)
1.11 Binary tree paths
- Text guide (Medium/Deeksha Sharma)
- Video guide (Nick White)
- Code example (OldCodingFarmer)
1.12 Island perimeter
- Text guide (MemoGrocery)
- Video guide (NeetCode)
- Code example (holyghost)
1.13 Find mode in binary search tree
- Text guide (Develop Paper)
- Video guide (Nick White)
- Code example (StefanPochmann)
1.14 Diameter of binary tree
- Text guide (After Academy)
- Video guide (NeetCode)
- Video guide (TECHDOSE)
- Code example (shawngao)
1.15 Maximum depth of N-ary tree
- Text guide (Medium/Annamariya Tharayil)
- Video guide (Nick White)
- Code example (user9918y)
1.16 Employee importance
- Text guide (LeetCode)
- Video guide (WorkWithGoogler)
- Video guide (Naresh Gupta)
- Code example (xuyirui)
1.17 Flood fill
- Text guide (Dev.to/Codingpineapple)
- Video guide (Kevin Naughton Jr.)
- Video guide (Nick White)
- Code example (shawngao)
1.18 Range sum of BST
- Text guide (Andrew Hawker)
- Video guide (Keving Naughton Jr.)
- Video guide (Nick White)
- Code example (rock)
2. Medium depth-first search interview questions
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.
2.1 Surrounded regions
- Text guide (After Academy)
- Video guide (NeetCode)
- Video guide (Nick White)
- Code example (Chronoviser)
2.2 Clone graph
- Text guide (Medium/Deeksha Sharma)
- Video guide (Michael Muinos)
- Video guide (NeetCode)
- Code example (mohamede1945)
2.3 Number of islands
- Text guide (Codertrain)
- Video guide (Kevin Naughton Jr.)
- Code example (girikuncoro)
2.4 Course schedule
- Text guide (Yu’s Coding)
- Video guide (NeetCode)
- Video guide (Nideesh Terapalli)
- Code example (varunu28)
2.5 Course schedule II
- Text guide (Zirui)
- Video guide (NeetCode)
- Video guide (Shiran Afergan)
- Code example (haoel)
2.6 Reconstruct itinerary
- Text guide (Medium/dume0011)
- Video guide (happygirlzt)
- Code example (StefanPochmann)
2.7 Path sum II
- Text guide (Medium/Len Chen)
- Video guide (DEEPTI TALESRA)
- Video guide (Kevin Naughton Jr.)
- Code example (OldCodingFarmer)
2.8 Flatten binary tree to linked list
- Text guide (After Academy)
- Video guide (NeetCode)
- Code example (tusizi)
2.9 Sum root to leaf numbers
- Text guide (Dev.to/Akhilpokle)
- Video guide (TECH DOSE)
- Code example (OldCodingFarmer)
2.10 Count complete tree nodes
- Text guide (Medium/Algo.Monster)
- Video guide (TECH DOSE)
- Code example (StefanPochmann)
2.11 Kth smallest element in a BST
- Text guide (LeetCode)
- Video guide (Kevin Naughton Jr.)
- Video guide (NeetCode)
- Code example (angelvivienne)
2.12 House robber III
- Text guide (Medium/Mollishree Soor)
- Video guide (NeetCode)
- Video guide (Algorithms Made Easy)
- Code example (jiangbowei2010)
2.13 Lexicographical numbers
- Text guide (Medium/codeandnotes)
- Code example (xialanxuan1015)
2.14 Evaluate division
- Text guide (Rusyasoft)
- Video guide (Lead Coding by FRAZ)
- Code example (GraceMeng)
2.15 Pacific Atlantic water flow
- Text guide (Dev.to/seanpgallivan)
- Video guide (NeetCode)
- Code example (bing28)
2.16 Path sum III
- Text guide (Dev.to/Andrew Hsu)
- Video guide (Timothy H Chang)
- Code example (wonderlives)
2.17 Most frequent subtree sum
- Text guide (Roger Wang)
- Video guide (Genetic Coders)
- Code example (lee215)
2.18 Find largest value in each tree row
- Text guide (EasyForces)
- Video guide (Nick White)
- Code example (Ryan777)
3. Hard depth-first 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.
3.1 Binary tree maximum path sum
- Text guide (After Academy)
- Video guide (NeetCode)
- Video guide (Michael Muinos)
- Code example (arkaung)
3.2 Alien dictionary
- Text guide (Medium/Feng Wang)
- Video guide (NeetCode)
- Video guide (happygirlzt)
- Code example (Tenderleo)
3.3 Serialize and deserialize binary tree
- Text guide (Baeldung)
- Video guide (Back To Back SWE)
- Code example (gavinlinasd)
3.4 Longest increasing path in a matrix
- Text guide (Dev.to/seanpgallivan)
- Video guide (Michael Muinos)
- Code example (yavinci)
3.5 Making a large island
- Text guide (Massive algorithms)
- Text guide (LeetCode)
- Video guide (Michael Muinos)
- Code example (lee215)
3.6 Minimize malware spread
- Text guide (LeetCode)
- Video guide (Ren Zhang)
- Code example (bupt_wc)
3.7 Sum of distances in tree
- Text guide (Tutorialspoint)
- Video guide (Timothy H Chang)
- Code example (lee215)
3.8 Binary tree cameras
- Text guide (Medium/Nerd For Tech)
- Video guide (Algorithms Made Easy)
- Code example (lee215)
3.9 Vertical order traversal of a binary tree
- Text guide (Techie Delight)
- Video guide (TECH DOSE)
- Code example (wangzi6147)
3.10 Critical connections in a network
- Text guide (Medium/Bhanuprakash)
- Video guide (Tech Revisions)
- Video guide (TECH DOSE)
- Code example (kaiwensun)
3.11 Maximum sum BST in binary tree
- Text guide (Medium/Gokul Ezhumalai)
- Video guide (Tushar Roy)
- Code example (yuhwu)
3.12 Frog position after T seconds
- Text guide (Tutorialspoint)
- Code example (lee215)
3.13 Tree of coprimes
- Text guide (EasyForces)
- Video guide (Cherry Coding)
- Code example (hiepit)
3.14 Minimize malware spread II
- Text guide (LeetCode)
- Video guide (happygirlzt)
- Code example (xxj79)
4. How to prepare for a coding interview
4.1 Refresh your knowledge
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only depth-first search but also the rest of the relevant algorithms and data structures. Check out our guides for detailed explanations and useful cheat sheets:
Algorithms explained:
- Depth-first search
- Breadth-first search
- Binary search
- Sorting
- Dynamic programming
- Greedy algorithm
- Backtracking
- Divide and conquer
Data structure guides:
4.2 Practice on your own
Once you’re confident in all of these, you’ll want to start working through lots of coding problems.
For depth-first search you can obviously use the questions we’ve listed above. For the other algorithms you need to know, check out the rest of this series:
- Breadth-first search interview questions
- Binary search interview questions
- Sorting interview questions
- Dynamic programming interview questions
- Greedy algorithm interview questions
- Backtracking interview questions
- Divide and conquer interview questions
We also recommend working through our list of 73 data structure interview questions. To get used to an interview situation, where you’ll have to code on a whiteboard, we recommend solving the problems on a piece of paper or google doc.
One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview. Of course, if it’s with someone else playing the role of the interviewer, even better.
4.3 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.
Any questions about depth-first search interview questions?
If you have any questions about depth-first search or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!