The Ultimate Guide to Solving BFS and DFS LeetCode Problems

Whenever I get asked about depth-first search (DFS) or breadth-first search (BFS) problems within an interview nowadays, I grin because of how generally easy these types of problems are to solve after I created and memorized my templates for DFS/BFS problems.

BFS/DFS problems are easy to do once you understand the basic mechanisms and “code templates” for solving problems.

BFS/DFS generally applies to problems related to 2D arrays, graphs, and trees. However, no matter what the problem medium is, the problem’s solution usually looks the same. By the end of the article, you’ll learn how to actually breeze through these types of problems using my mental model/template for solving these types of problems.

DFS and BFS problems come up often during software engineer interviews, so it’s worth understanding how to solve them on a deeper level than other greedy-solution problems. In other words, you should make sure that you understand DFS and BFS problems within your LeetCode interview preparation.

How to Identify DFS/BFS Type Problems

The first thing you need to know to solve DFS/BFS problems is how to identify them. Without thinking of the code implementation details, DFS/BFS solutions should be easy to identify once you solve enough problems that work with them. 

The key solution setups you’ll want to look for are the need to find a single or cumulative value(s) by searching a given space, the need to traverse a space level-by-level, and retrieving the number of iterations it takes to move from position A to position B within space.

NOTE: Code templates for DFS and BFS solutions will be shown AFTER this section on identifying DFS and BFS type problems.

DFS and BFS in Tree Problems

Binary or n-ary tree problems have nodes linked to each other in a unidirectional way, forming a DAG (directed acyclic graph). Each node also has at most one parent.

How to Identify Depth-first Search Tree Type Problems

In Figure 1, we see an iteration of a DFS search upon the root node following a pre-order traversal.

In Figure 2, we see a later iteration of the same DFS search the root node following pre-order traversal rules.

The important thing to recognize here is the movement of the DFS algorithm within a tree. When you’re trying to identify if a DFS algorithm can be used, I find it especially useful to visualize my thought process as in Figures 1 and 2 above.

Solutions we can derive from the DFS from a binary tree’s (or more generally n-ary tree) include:

1. Is certain value within the tree?
   • The DFS traverses the whole tree, so we can figure this out
2. What is the sum of the values of the tree leaf elements
   • The DFS traverses all of the leaves, so we can figure this out
3. What is the maximum sum that can be computed between tree leaf elements
   • If you DFS on both the left side and right side for each node, you’re able to derive this value

How to Identify Breadth-first Search Tree Type Problems

The BFS algorithm allows you to traverse a tree’s solution space level-by-level. Depending on the question, the “levels” could represent something like time or the number of steps within a problem. Alternatively, some problems are just easier to solve when you traverse a tree in a BFS way.

In Figure 1 above, assuming the root node is the top node, each breadth or level is depicted by the number before the period. The ordering within each breadth is based on the number after the periods.

In Figure 2 above, I express a variation of a type of tree problem that can arise during interviews. If the problem was to find all nodes that are 2 nodes away from the node labeled 1.0, using a BFS search upon the tree would solve this problem because we would be able to get the solution to this problem on the 2nd breadth of the search. We’d just need to convert the representation of the binary tree into a graph (aka make the nodes accessible in a bi-directional way).

Some examples of identifying when to use a BFS traversal on a tree-type problem:

• Return the tree nodes as viewed from either the left or right side
  • The BFS level-by-level search allows you to have access to the first/last element that you need
• Serialize a binary tree into an array
  • Assuming the root is 1-indexed (instead of 0-indexed) and at index 1 of the resulting array, every node could have its left child at index “index * 2” and its right child at index “(index * 2) + 1”.
• Find all nodes that are N distance away from node A
  • Morphing the tree into a graph example was described above

DFS and BFS in Graph Problems

Graphs are like trees with the exception of the ability to have their nodes linked to each other in a non-unidirectional way. 

How to Identify Depth-first Search Graph Type Problems

If you’ve read and understood the previous section about identifying depth-first search problems within tree problems, then identifying the DFS graph type should be relatively easy.

Depth-first search graph-type problems are as easy to identify as tree-DFS problems because trees are a type of graph. Graphs are like trees (in terms of having connected nodes) except they’re not bounded by tree-specific rules. Any node within a graph can connect with any node.

How to Identify Breadth-first Search Graph Type Problems

A lot of the time, graph problems are difficult to solve because they’re not explicitly about graphs (like in tree problems). Algorithmic problems that involve graphs usually have setups that don’t explicitly mention a graph but can be solved using a graph representation.

This is especially important for BFS solutions to graph problems. If you’re unable to identify how to translate a problem’s requirements and setup into a graph problem, you’re not going to have a chance to apply a BFS solution.

In the figure above (relating to BFS solutions), you can see an example of BFS on the graph, structured in a similar way to the above BFS figures for tree problems.

Some examples of identifying when to use a BFS traversal on a graph-type problem:

• How many steps will it take to get to a node in a graph?
  • — longer explanation later in the article
• Does a value exist in a graph (similar to identifying DFS solutions — Many times, DFS or BFS will work depending on the problem)

DFS and BFS in Array Problems

Typically, array problems that include DFS or BFS solutions involve navigating across a 2D array in either a 4-way-directional or 8-way-directional way.

How to Identify Depth-first Search Array Type Problems

The figure above depicts a search from the top left corner of the 2D array to the green space.

An array-based problem may have a DFS solution if the problem revolves around pathfinding or filling an area. These types of problems tend to include constraints such as blockers (similar to the black square blocks on the 2D array representation) or movement variations (4-way, 8-way, or other).

How to Identify Breadth-first Search Array Type Problems

Breadth-first search array-type problems can be identified by the need to search for something(s) and count and/or utilize concepts like levels, time, or steps.

The figure above depicts a yellow starting location, 2 green destinations, and 2 black grid locations which act as traversable areas. If the question was to find the minimum number of steps (only being able to move up, down, left, or right) to reach all the destinations, a BFS solution could be used to find that by the 5th breadth/level, all destinations are reached.

How to Easily Solve Depth First Search (DFS) Problems

To solve problems using DFS, you can use a simple template of exiting early if necessary, pushing the first valid location onto a stack, handling the current element from the stack, and then adding the next logical unseen and unprocessed elements to the stack.

Above is an annotated valid solution to the problem Max Area of Island which will be used as an example.

1. Exit early
   • This phase is about only doing a DFS on valid starting locations. For this problem, a valid starting location must be unvisited, and a 1.
2. Push first valid elements
   • The first valid element, in this case, is the position you’re starting the DFS with.
3. Handle current element
   • This step changes based on the problem. Because we’re counting the area of an island (defined as the number of 1s connected in 4 ways, the handling in this case is the increment of the currentArea counter by one.
4. Add next logical element(s)
   • The next logical elements, in this case, are valid positions that haven’t been visited, haven’t been added to the stack yet, and are 1s

This is the logical structure for the vast majority of DFS problems related to trees, graphs, and 2D arrays.

How to Easily Solve Breadth First Search (BFS) Problems

To solve problems using BFS, you can use a simple template of exiting early if necessary, pushing the first valid location onto a queue, handling the next breadth of the BFS, handling the current element from the queue, and then adding the next logical unseen and unprocessed elements to the queue.

Above is an annotated valid solution to the problem Binary Tree Level Order Traversal which will be used as an example.

1. Exit early
   • If the root is null, a BFS cannot be done.
2. Push first valid elements
   • The root is the first and only element.
3. HL (aka Handle Level)
   • Because we want to build lists of each of the levels, we’ll need to keep track of the number of nodes in each of the levels before we start modifying the queue. Otherwise, we don’t know when to stop.
   • For each breadth as well, we’ll need a new sub-result array to add elements of the same breadth/level into.
   • Lastly, we’ll need to add each of the sub-results into the main result after each breadth.
4. Handle current element
   • Handling the current element in this case is just adding the element’s value into the sub-result which will contain all of the values within the current level or breadth.
5. Add next logical element(s)
   • In the case of a tree, the next logical unvisited/unprocessed elements are the left and right children if they exist. We don’t need to check if we’ve visited them before because we’re dealing with a tree data structure that is unidirectional. If this was a graph or an array that we could traverse back and forth, some sort of “visited” check might be necessary.

As an additional example of a BFS for a graph problem, I think a great example of this is the problem called Open the Lock. In this problem, you have to return the minimum number of steps to get from the initial position of a lock to an unlocked position (given some constraints as well).

This is a great example of a problem that’s not explicitly given as a graph but can be transformed into one.

Above is a code snippet of a working solution to the problem. Below is an image that illustrates a simplified version of the problem represented as a graph (it is easier to digest the information that way).

• Exit early
  • If the unlocking process cannot start because 0000 is jammed, then exit early
• Push first valid elements
  • The first valid element or lock position to BFS is 0000
• HL (aka Handle Level)
  • Because we want to build lists of each of the levels, we’ll need to keep track of the number of lock positions in each of the levels before we start modifying the queue. Otherwise, we don’t know when to stop.
  • At the end of each level, we want to increment the current as well.
• Handle current element
  • For each element, we’ll need to know if we’re at the destination lock position to return to the current level we’re on.
• Add next logical element(s)
  • The next “logical unprocessed/unseen” elements are the next lock positions we can go to if we move a digit up or down. This also includes a bit of logic to make sure we wrap around. If we move down from digit 0 it goes to 9 instead of -1. If we move up from digit 9 it goes to 0 instead of 10.
  • If we’ve seen a position before, we don’t add it to the queue again.