Data Structures and Algorithms: Depth First Search

Introduction

In Depth First Search(DPS), we use an algorithm to traverse data structures such as trees and graphs. Starting with the root node, we traverse as deeply as possible on a branch(arriving at a leaf) before backtracking to a parent node and visiting its other children nodes. In code, this can either be done iteratively or recursively.

Types of Traversal

Traversal is the process by which we can visit each and every node within in a tree. I will use the following tree to demonstrate the 3 types of traversal in a DPS.

1. Pre-order

In a pre-order traversal, we print out the value of the parent node before printing out the values of the children nodes. Here is some pseudocode showing the process.

visitNode() 
recurseLeft()
recurseRight()

Here is some code showing how pre-order traversal can be achieved iteratively using a stack.

const preOrderTraversal = (root) => {
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    console.log(node.val);
    if (node.right !== null) {
      stack.push(node.right);
    }
    if (node.left !== null) {
      stack.push(node.left);
    }
  }
};

The current node is pushed onto the stack and its value is printed out. If the current node has children, they are pushed onto the stack, starting with the right child followed by the left child.

Alternatively, the same result can be achieved recursively. A good base case will be when the tree is empty, that is to say, when it has no leaves. This can be done as follows:

const preOrderTraversal = (root) => {
  if (root === null) {
    return;
  }

  console.log(root.val);
  preOrderTraversal(root.left);
  preOrderTraversal(root.right);
};

Using the above binary tree as an example, the result of a pre-order traversal will be: 4, 21, 5, 8, 7, 13, 2.

It is worth noting that the root will always be at the beginning of a pre-order traversal.

2. In-order

In the case of an in-order traversal, we start at root and go left as deep into the tree as possible. When we reach a leaf(a node with no children), we print its value, print the value of the parent and then the value of the right leaf. The process is then repeated up the tree. The following is the pseudocode:

recurseLeft()
visitNode() 
recurseRight()

As with the pre-order traversal, an in-order traversal can also be achieved iteratively:

const inOrderTraversal = (root) => {
  const tempStack = [];
  const inOrder = [];

  while (true) {
    if (root !== null) {
      tempStack.push(root);
      root = root.left;
    } else {
      if (tempStack.length === 0) break;

      root = tempStack.pop();
      inOrder.push(root.val);
      root = root.right;
    }
  }
  return console.log(inOrder);
};

An in-order traversal can also be achieved recursively:

const inOrderTraversal = (root) => {
  if (root === null) {
    return;
  }

  inOrderTraversal(root.left);
  console.log(root.val);
  inOrderTraversal(root.right);
};

Using the above binary tree as an example, the result of an in-order traversal will be: 5, 21, 8, 4, 13, 7, 2. It is interesting to note that the root will always be somewhere in the middle of an in-order traversal.

3. Post-order

As for a post-order traversal, we start at the root and go left until we reach a leaf. The value of this leaf is printed and then we go back up one and then go right, printing the value of the right leaf. Finally we go back up and print the value of the parent, before repeating the process ip the tree. Here is the pseudocode:

recurseLeft()
recurseRight()
visitNode()

This is how a post-order traversal can be achieved iteratively utilizing a stack and an array:

const postOrderTraversal = (root) => {
  if (!root) return [];

  const tempStack = [root];
  const postOrder = [];

  while (tempStack.length) {
    const node = tempStack.pop();

    postOrder.unshift(node.val);

    if (node.left) {
      tempStack.push(node.left);
    }
    if (node.right) {
      tempStack.push(node.right);
    }
  }
  return console.log(postOrder);
};

Here we use the temporary stack,tempStack, to keep track of the nodes to be visited. In each iteration we remove a node from this temporary stack and add its value to the postOrder array. If children nodes exist, they are pushed onto the temporary stack.

Similar to the previous two types of traversal, a a post-order traversal can also be achieved recursively:

const postOrderTraversal = (root) => {
  if (root === null) {
    return;
  }

  postOrderTraversal(root.left);
  postOrderTraversal(root.right);
  console.log(root.val);
};

Using the above binary tree as an example, the result of a post-order traversal will be: 5, 8, 21, 13, 2, 7, 4.
It is also worth noting that the root will always be at the end of a post-order traversal. This is because we will visit and print the values of all of the children before printing out the value of the parent node.

Conclusion

This concludes the three types of traversal that can be used in a depth first search. The implicit data structure used here is a stack. A depth first search can be useful when you want to compare the shape and structure of two trees.