binary-tree-depth-first-search.js

/**
 * Depth first search and Breadth first search traverals in JavaScript
 * This example uses a binary tree with left and right nodes
 * by theptrk <github.com/theptrk> 
 */
function Node(value, opts = {}) {
  this.value = value
  this.left = opts.left ? opts.left : null
  this.right = opts.right ? opts.right : null
}

var root = new Node('a', {
            left: new Node('b'),
            right: new Node('c', {
              left: new Node('d', {
                left: new Node('f'),
                right: new Node('g', {
                  left: null,
                  right: new Node('h')
                })
              }),
              right: new Node('e')
            })
          })

/**
 * The tree looks like this:
 * 
 *           node('a')
 * node('b')                 node('c')
 *                 node('d')         node('e')
 *            node('f')  node('g')
 *                         node('h')
 */

/**
 * Depth first search: prototype function (method) : recursive
 * This function will short circuit on the check based on left nodes
 * Note that we need to check for the existence of the left and right nodes
 */
Node.prototype.dfs = function(target) {
  if (this.value === target) {
    return true;
  }
  // Optimization: here we evaluate left before right, 
  // Note this is NOT done lazily in JavaScript
  var inLeft = this.left === null ? false : this.left.dfs(target);
  if (inLeft) {
    // we optimistically return from evaluating left node 
    return inLeft
  }
  var inRight = this.right === null ? false : this.right.dfs(target);
  if (inRight) {
    return inRight
  }
  return false;
}

/**
 * Depth first search: prototype function (method) : iterative
 * This is solved by using a stack for its LIFO property 
 */
Node.prototype.dfsIterative = function(target) {
  var stack = [];
  // our first node in the stack is the current node, typically the root
  stack.push(this);

  while (stack.length > 0) {
    // we process nodes from the "top" of the stack
    var lifoNode = stack.pop();

    if (lifoNode.value === target) {
       return true; 
    }
    // note, since we are using lifo, our right nodes must 
    // be push first (left nodes will be on top of the stack)
    if (lifoNode.right) {
      stack.push(lifoNode.right);
    }
    if (lifoNode.left) {
      stack.push(lifoNode.left);
    }
  }
  // if we reach this point, all child nodes from this node have been visited
  return false;
}

/**
 * Breadth first search: prototype function (method) : iterative
 */
Node.prototype.bfs = function(target) {
  var queue = [];
  // our first node in the stack is the current node, typically the root
  queue.push(this)

  while (queue.length > 0) {
    // we process nodes from the "front" of the queue
    // an optimized queue back by a linked list can be used here
    fifoNode = queue.shift()

    if (fifoNode.value === target) {
      return true;
    }
    // note, since we are using fifo, our left nodes must pushed first;
    // immediate left nodes will be processed before immediate right notes
    if (fifoNode.left) {
      queue.push(fifoNode.left)
    }
    if (fifoNode.right) {
      queue.push(fifoNode.right)
    }
  }
  return false;
}