Depth First Search (Javascript)

Let’s get into it.

When we traverse a tree with DFS, we are searching the bottommost level of the tree and then returning to the root from left to right.

To create a tree:

class Node {
   constructor(val) {
     this.val = val;
     this.left = null; 
     this.right = null;
  }
}

Then add your values to a tree:

const a = new Node (1)
const b = new Node (2)
const c = new Node (3)
const d = new Node (4)
const e = new Node (5)
a.left = b
a.right = c
b.left = d
b.right = e
        1
       / \
      2   3
     / \
    4   5      

Once your tree is configured, you can traverse it (here it is iteratively):

const DFS = (root) => {
   //make an empty array to house the root
   let queue = [root]
   //create an empty array to house the visited values
   let stack = []
   //create a while loop and the logic: "while the stack is greater than 0"
   while (queue.length > 0) {
     
     //create a variable = to the popped off iteration
     let current = queue.pop()
     //push the visited value into the stack     
     stack.push(current.val)
     //loop through the left and right if there is a left and right
      if (current.left) {
       //if there is a left, push it into the stack
        queue.push(current.left)
      }
     if (current.right) {queue.push(current.right)}
}
   return stack
}

Here is the recursive version!

const DFS = (root) => {
   //create your base case(s)
   if (root === null) return []
   //create your variables that recursively call the left and right
   let left = DFS(root.left)
   let right = DFS(root.right)
 
   //use the spread operator to return an array of the current       //value, the left and the right values
   return [root.val, ...left, ..right]
}

Happy hacking!