50+ depth-first search (DFS) interview questions [easy, medium, hard]

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:

  1. Easy depth-first search interview questions
  2. Medium depth-first search interview questions
  3. Hard depth-first search interview questions
  4. 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
1.2 Same tree
1.3 Symmetric tree
1.4 Maximum depth of binary tree
1.5 Balanced binary tree
1.6 Path sum
1.7 Binary tree preorder traversal
1.8 Binary tree postorder traversal
1.9 Invert binary tree
1.10 Lowest common ancestor of a binary search tree
1.11 Binary tree paths
1.12 Island perimeter
1.13 Find mode in binary search tree
1.14 Diameter of binary tree
1.15 Maximum depth of N-ary tree
1.16 Employee importance
1.17 Flood fill
1.18 Range sum of BST

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
2.2 Clone graph
2.3 Number of islands
 2.4 Course schedule
2.5 Course schedule II
2.6 Reconstruct itinerary
2.7  Path sum II
2.8 Flatten binary tree to linked list
2.9 Sum root to leaf numbers
2.10 Count complete tree nodes
2.11 Kth smallest element in a BST
2.12 House robber III
2.13 Lexicographical numbers
2.14 Evaluate division
2.15 Pacific Atlantic water flow
2.16 Path sum III
2.17 Most frequent subtree sum
2.18 Find largest value in each tree row

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
3.2 Alien dictionary
3.3 Serialize and deserialize binary tree
3.4 Longest increasing path in a matrix
3.5 Making a large island
3.6 Minimize malware spread
3.7 Sum of distances in tree
3.8 Binary tree cameras
3.9 Vertical order traversal of a binary tree
3.10 Critical connections in a network
3.11 Maximum sum BST in binary tree
3.12 Frog position after T seconds
3.13 Tree of coprimes
3.14 Minimize malware spread II

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:

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:

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.

cta_illustration arrow_left Browse FAANG ex-interviewers

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!