algorithms: depth first search (dfs)

When it comes to searching a tree, there are two general approaches: depth first and breadth first.

This post will discuss the former and some general approaches to thinking about it. I’ll discuss both an iterative and recursive approach and how I think about them.

What Is A Depth First Search?

In tree-like data structures (binary search trees, the DOM, etc.), it can be useful to traverse a tree starting at a target node. This target can be the root, like the html tag in the DOM, but you can also select a specific node (e.g., document.getElementById('right-nav')).

A depth first search iteratively searches each path from the target node to each leaf.

Let’s look at an example to make this more concrete:

               a
         /           \
      b               c
   /     \         /      \
  d       e       f        g
 /  \    /  \    /   \    /   \
h    i  j    k  l     m  n     o

A depth first search starting at node a would typically start by traversing the left nodes and then work rightward. For example:¹

a
ab
abd
abdh
abdi
abe
abej
...

Why Use A Depth First Approach (vs. Breadth First)

Ultimately, both approaches will work as they both search the entire tree. The advantages of the depth first approach come through in larger trees where the solution is farther from root. This is largely due to the lower memory requirements of this approach relative to breadth first.²

Iterative Depth First Traversal

To iteratively traverse a tree depth first, we will use a stack as a data structure. Because we’re using a stack, the order of processing the children of nodes matters. Specifically, if we want to go left to right, then we will need to add the right most child nodes to the stack first.

This looks a little like this:

1. Given a node
2. If the node has a right child, add the right node to the stack
3. If the node has a left child, add the left node to the stack

Since stacks are last-in first-out, when we “pop” the top off the stack, we’ll be looking at the left node first. As we rinse and repeat, we’ll continue along the left edge of the tree all the way to the leaf (i.e. a node that has no children ).

interface Node {
  value: number
  leftChild: Node
  rightChild: Node
}
function iterativeDFS(node: Node) {
  const stack = []
  stack.push(node) // "seed" the stack with the root node
  while (stack.length) {
    const current = stack.pop() // now we have access to the actual node

    // specific action we want to take, e.g., if leaf - evaluate if path leaf matches criteria

    current.rightChild && stack.push(current.rightChild)
    current.leftChild && stack.push(current.leftChild)
  }
}

I am specifically not describing what we’re doing with the search as the number of use cases are infinite. Instead, I’m demonstrating how to use a stack to keep track of children.

Recursive Depth First Traversal

In many respects, the recursive approach is very similar to the iterative one. For each level of the tree, we look to see if there are children and decide what we want to do.

The difference is that this time, we’ll call a new function to process it. In practice, I find that this typically benefits from using closure as it’s almost always the case that the base case of the recursion will need more than just the node to determine the result (and I’d prefer to keep the public API as simple as possible).

Again, the order of processing the child nodes matters, however with the recursive approach it is more intuitive - to go left, process left first.

This looks a little like this:

1. Given a node
2. If the node has a left child, call the same function using the left node as its target
3. If the node has a right child, call the same function using the right node as its target

interface Node {
  value: number
  leftChild: Node
  rightChild: Node
}
function recursiveDFS(node: Node) {
  if (!node.leftChild && !node.rightChild) {
    // base case - we've reached a leaf
  }
  node.leftChild && recursiveDFS(node.leftChild)
  node.rightChild && recursiveDFS(node.rightChild)
}

The above example is not using the closure I referred to above, assuming that all I would require is a node.

Two notes for using recursive functions:

1. Always define your base case first to avoid a stack overflow

2. Since each function call adds another function to the call stack, it’s important to manage the return values. For example, in our function above, even if the base case includes a return - if the tree is more than one level deep, the final returned value will always be undefined.

   This is also not easily addressed because we want to be sure to recurse through all children. It’s around this time that I find myself reaching for closure to track additional variables with each call and be sure that I can return the appropriate values.

   An enduring challenge is early returns. For example, if you are finding the first solution, not counting all solutions, then a recursive approach may add wrinkles.

Handling Non-Binary Trees

A quick note on non-binary trees. The solutions for both iterative and recursive depth first traversal look very similar if each node can have a list of children instead of just a left or right.

I won’t detail too much as I’ve already discussed both approaches, however, I will note that I did not force myself to search left to right on the iterative approach as there’s no native, non-destructive, way in Javascript to reverse an array (without duplicating the list - which didn’t feel worth it).

Without further ado - an iterative and recursive approach for depth first searching non binary trees:

interface Node {
  value: number
  children: Node[]
}
function recursiveDFS(node: Node) {
  const stack = []
  stack.push(node)

  while (stack.length) {
    const current = stack.pop() // now we have access to the actual node

    // specific action we want to take, e.g., if leaf - evaluate if path leaf matches criteria

    current.children.forEach((child) => stack.push(child)) // note - this will now search right to left!
  }
}

interface Node {
  value: number
  children: Node[]
}
function recursiveDFS(node: Node) {
  if (!node.children.length) {
    // base case - we've reached a leaf
  }
  node.children.map((child) => recursiveDFS(child))
}

Conclusion

I wanted to write this post because even though I’ve learned to search a tree depth first a number of times, it always takes me a few minutes to remember how it works the first time I see it after a hiatus.

At this point, I’m pretty good at recognizing when I need to traverse a tree depth first. The issue is those few small mechanics of actually implementing the stack or recursive approach. With this post, I now have a resource to reference exactly those pieces without concerning myself with the overhead of the specific problem.

Footnotes

• ¹ I say typically, because, of course, this is implementation specific.
• ² In the worst case, implementation depending, the memory requirement is O(h),where h is the height of the tree. For a binary tree this is equivalent to ~O(log(n)) as the height of a binary tree is equal to log base two of the sum of the number of nodes and one. In contrast, a breadth first approach’s worst case is O(n).