What is depth limited search?

The depth limited search is a variation of a well-known depth first search(DFS) traversing algorithm. It takes care of an edge case problem with DFS by implementing a depth limit.

The DFS algorithm

To implement DFS with a stack, we use these steps:

1. We push the root node into the stack.
2. We pop the root node before pushing all its child nodes into the stack.
3. We pop a child node before pushing all of its nodes back into the stack.
4. We repeat this process until we either find our result or traverse the whole tree.

The problem with DFS

Let’s say we are working with a tree whose height is either very large or infinite. In such a case, our DFS algorithm would also go on infinitely, as there would always be more child nodes to push back into the stack.

This is what the depth limited search aims to address with a level limit variable.

Example

Let’s look at the following tree with six nodes. Our target node is 5. For this example, we’ll use a level limit of two as we traverse the tree.

We use a visited array to mark off nodes we have already traversed through. This keeps us from visiting the same node multiple times.

Code explanation

• We follow normal DFS and start with the root node 1 at level 0.
• We mark it visited and add its children nodes, 2 and 3, to the stack. We increment our level by 1.
• Node 2 is at the top of our stack. We add its children, 4 and 5, to our stack. We increment our level by 1. Our level counter is now 2.
• Node 4 is at the top of our stack. We can add its child node 6 to our stack. However, doing so would exceed our level counter, so we ignore Node 6.
• Node 5 is at the top of our stack. It has no children to append to our stack.
• Node 5 is our desired result, so the algorithm stops.

When depth limited search fails

As we can see, we ignore Node 6 as it was below our level limit. So, what would happen if our desired node was 6 all along?

This is known as a cutoff failure. Our target exists, but it is too deep for us to traverse.

Let’s suppose our level limit was 3 instead, and our desired node was 7. We could traverse the whole tree without finding our result. That would be a standard failure.

Time complexity

The time complexity of depth limited search is $O(V^L)$. Where $V$ is the number of nodes and $L$ is the level limit.