Depth First Search

depthFirstSearch.JS

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

Node.prototype.toString = function() {
  return this.value;
}  

Node.prototype.depthFirstSearch = function depthFirstSearch(rootNode) {
  if (rootNode === null) {
    return;
  }
  
  // Print the data of the node.
  console.log(rootNode.value);
  
  depthFirstSearch(rootNode.left);
  depthFirstSearch(rootNode.right);

}

The depth-first algorithm sticks with one path, following that path down a graph structure until it ends. The depth-first search algorithm allows us to determine whether two nodes, node x and node y, have a path between them. The DFS algorithm does this by looking at all of the children of the starting node, node x, until it reaches node y. It does this by recursively taking the same steps, again and again, in order to determine if such a path between two nodes even exists.

Applications of DFS:

• Topological ordering of nodes: Topological ordering of a directed graph is a linear ordering of vertices such that for every directed edge uv, u comes before v in the ordering. This is useful in situations where you want to enforce dependencies e.g. task A must be done before task B which must be done before task C)
• Path finding: We can the DFS algorithm to find a path between 2 vertices in a graph u and v. Basically we start at the start vertex and use a stack to keep track of the path between the start and end vertex. Once we get to the end vertex, we return the path as the contents of the stack.

Most DFS algorithms use a stack to implement however in our case we are using a recursion.