Algorithms: Depth-first Search
Published: 2020-11-20 16:17:36

The depth-first search problem was great practice involving a tree.  My initial attempts at the solution were iterating through in essentially a breadth-first search way, but after working through it, I managed to figure out how to use recursion in order to drill all the way down one branch before moving to a sibling node. 

[Here](https://en.wikipedia.org/wiki/Depth-first_search#:~:text=Depth%2Dfirst%20search%20(DFS),along%20each%20branch%20before%20backtracking.) is a quick definition of depth-first search.

<b>Problem</b>

We're given a `Node` class with a `name` and an array of optional `children` nodes. The nodes form a tree structure.

We're tasked with implementing the `depthFirstSearch` function on the `Node` class, and the function takes in an empty array. The function is supposed to traverse the tree with the Depth-first Search approach, store all of the nodes' names in the array and return the array.

Our tree will look like this:

```
     A
   / | \
  B  C  D
 / \   / \
E  F  G   H
  / \  \
 I   J  K
```

With the depth-first search approach, we want to return an array that looks like this:

```
["A", "B", "E", "F", "I", "J" "C", "D", "G", "K", "H"]
```


<b>Approach</b>

We want to add all of the nodes' names in one branch to the final array before moving on to the next branch. So first, we start at root node "A", then go to its first child "B", then go to the child of "B", which is "E". Those names are now all in the array. There are no children of "E", so once we complete that branch, we go back up to "B" and check if it has other child nodes. "B" does have another child "F". We add "F" and check if it has children, and it does. We add its child "I", check if it has children, and it does not. We go back up to "F" and add its child "J" to the array. "J" does not have children so we go back up to "F", which has no more children, go back up to "B" which has no more children, so we're back at "A". We repeat the process with "C", and then "D".

We'll be using a for loop and a recursive approach to solve this problem. 

The way I approached it was by keeping track of a `currentNode` throughout the function. First step is to add the `currentNode`'s name to the array. Then we loop through the children of the currentNode, and we recursively call the `depthFirstSearch` function again on any child nodes of the currentNode. This is how we drill down the same branch and add all the children on one branch to the array before moving to the next sibling of the `currentNode`.

Lastly, we return the array with all of the node names.

<b>Solution</b>
We're working on the function `depthFirstSearch` within the given `Node` class. This gives us access to the `this` keyword, to reference the `currentNode` instance we are working with. 

```
class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }

depthFirstSearch(array) {

  }
}
```

We have access to `this`, so I saved it to a variable `currentNode` for easy tracking.

```
depthFirstSearch(array) {
  let currentNode = this;
}

```

We push the `currentNode`'s name into the array. 

```
depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
}

```
Next, we begin our for loop to iterate through our `currentNode`'s children.

```
depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
  for (let child of currentNode.children) {

  }
}
```
This part is key, because our recursion occurs in the for loop.

As we loop through each child, we reassign `currentNode` to be the `currentNode`'s child. Next step is we call the `depthFirstSearch` function on that child. This means we go through the function again, but with this child node instead. We add that child node's name to the array, then we enter the for loop and iterate through that child node's children, and repeat the process.

```
depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
  for (let child of currentNode.children) {
    currentNode = child;
    currentNode.depthFirstSearch(array);
  }
}
```

Lastly, we return the array for our answer. 

```
depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
  for (let child of currentNode.children) {
    currentNode = child;
    currentNode.depthFirstSearch(array);
  }
  return array;
}
```

Inside the `Node` class, it looks like this:

```
class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }

depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
  for (let child of currentNode.children) {
    currentNode = child;
    currentNode.depthFirstSearch(array);
  }
  return array;
 }
}
```

<b>Resources</b>

-[AlgoExpert](algoexpert.io)

-[Stephen Grider's Udemy DS & Algorithms Course](https://www.udemy.com/course/coding-interview-bootcamp-algorithms-and-data-structure/)

-[Wikipedia](wikipedia.org)