Understanding the Different Strategies of Depth First Search Tree Traversal

Depth First Search (DFS) tree traversal can be performed with any of the following strategies: "in-order", "post-order", and "pre-order". What's the difference? The difference is actually quite simple - it is simply the order in which you visit the node compared to when you traverse the children of the node.

The Basics

To better understand what this means, let's talk about the basics of tree traversal. For simplicity, we'll assume we're only working with binary trees where each node can have at most two children, a left child and a right child.

For each node of the binary tree, there are three steps to complete:

• traverse the left subtree
• traverse the right subtree
• do something with the node itself - here we'll record it's value

So with these three steps established, we can place them in their correct order for each DFS strategy:

Pre-order:

In pre-order, we first process the node:

1. Do something: record the node's value
2. Traverse the left
3. Traverse the right

Post-order:

In post-order, we process the node last:

1. Traverse the left
2. Traverse the right
3. Do something: record the node's value

In-order:

For in-order, we'll process the node in between traversing each side:

1. Traverse the left
2. Do something: record the node's value
3. Traverse the right

As we can see from the steps above, we do the exact same thing in each strategy, just in a slightly different order. This means we can use the same lines of code for each method. We'll just need to make a slight alteration in the order.

The Code

Tree Structure

We'll assume we have a Binary Tree class that looks something like this Binary Search Tree:

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(val) {
    const newNode = new Node(val);

    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let curr = this.root;

    while (true) {
      if (curr.val > val) {
        if (!curr.left) {
          curr.left = newNode;
          return this;
        }

        curr = curr.left;
      } else if (curr.val < val) {
        if (!curr.right) {
          curr.right = newNode;
          return this;
        }

        curr = curr.right;
      }  else {
         return this;
      }
    }
  }
}

Depth First Search Pseudo Code

We will write a function that accepts a node (the root of a tree on the first pass) and returns an array of all the values in that tree, after visiting all of the nodes once. Here, we'll use a recursive strategy.

• Our function will create an array, visited, to record the values of visited nodes.
• Our base case will check if the node is null. If so, we'll return the empty array.

• Otherwise we need to perform our three steps:

  • add the value of the node to the visited array
  • Recursively call our function again, passing in the left child as the node and concatenating the return value of this function call to the visited array
  • Recursively call our function again, passing in the right child as the node and concatenating the return value of this function call to the visited array

• After visiting all nodes in the tree, the visited array will be filled with the values of each node.

• Finally, we will return visited.

Depth First Search Function

For Pre Order (visit the node first) this looks like:

function dfsPreOrder(node) {
  let visited = [];

  if (!node) return visited; //base case

  visited.push(node.val); //1. visit node
  visited = visited.concat(dfsPreOrder(node.left)) //2. traverse left
  visited = visited.concat(dfsPreOrder(node.right)) //2. traverse right

  return visited;
}

For Post Order (visit the node last) this looks like:

function dfsPostOrder(node) {
  let visited = [];

  if (!node) return visited; //base case

  visited = visited.concat(dfsPostOrder(node.left)) //1. traverse left
  visited = visited.concat(dfsPostOrder(node.right)) //2. traverse right
  visited.push(node.val); //3. visit node

  return visited;
}

For In Order (visit the node in the middle) this looks like:

function dfsInOrder(node) {
  let visited = [];

  if (!node) return visited; //base case

  visited = visited.concat(dfsInOrder(node.left)) //1. traverse left
  visited.push(node.val); //2. visit node
  visited = visited.concat(dfsInOrder(node.right)) //3. traverse right

  return visited;
}