Depth First Search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

Tree Structure
See the page on trees for an example of how we implement tree data structure in Javascript.

function Node (value) {
  this.value=value;
  this.left=null;
  this.right=null;
}

Depth First Search Algorithm – Recursion
Recursion is the simpler way of implementing DFS because you don’t need to keep track of what’s left to visit.
The strategy to implement DFS algorithm is understanding what DFS is supposed to do. It goes down a path as far as possible first, then backtracks and repeats.

  1. Start at Root Node (or some arbitrary node if graph)
  2. Go down as far as possible on a branch (typically left most branch)
  3. Repeat at the right node of that branch
  4. If graph, keep track of what’s been visited and skip that

DFS Recursion in Javascript – Binary Tree
Here’s a Javascript implementation of Depth First Search:

function DFS (node) {
  //process current node
  console.log(node.value);

  if (node.left) {
    DFS (node.left); //visit left node
  }

  if (node.right) {
    DFS (node.right); //visit left node
  }
}

DFS is a recursive function.
If left node is available we go there and run DFS again. That’ll keep going until we get to the end of the branch on the left side.
At the bottom left node, it’ll run the code to process the current node, here which we just console log the value of that node.
Then we go to the right node if available and run DFS on that. Note that it doesn’t keep going on the right hand side until the end; at the next DFS iteration it’ll run the left hand side first. In other words, when it goes right, it’ll still check left at that next child node first.

DFS Iterative in Javascript
As before, we want to travel down one branch until the end before backtracking. So how do we do this in Javascript without recursion?

function DFS (node) {
  let stack=[node]; //LIFO: Last In, First Out
  while (stack.length>0) { //while stack isn't empty
    const current=stack.pop(); //take from top of stack

    //process current node
    console.log(node.value);

    if (current.left) {
      stack.push(current.left); //add to stack
    }
    if (current.right) {
      stack.push(current.right); //add to stack
    }
  }
}

Difference between BFS and DFS
Fundamentally, the difference between DFS and BFS is that with a DFS you push the children of the current node onto a stack, so they will be popped and processed before everything else, while for BFS you push the children onto the end of a queue, so they will be popped and processed after everything else.