Binary Search Tree and Depth First Traversal in Javascript

binary-search-tree-dfs.js

class BinarySearchTree {
  
  constructor(){
    this.root = null;
  }
  
  // add a node to the tree
  add(value){
    let newNode = { value, left: null, right: null};
    
    // set the root if we don't have one
    if(this.root == null){
      this.root = newNode;
      return;
    }
    
    let current = this.root;
    
    while(true){
      // check for right
      if(value > current.value){
        // add right
        if(!current.right){ current.right = newNode; break; }
        
        current = current.right;
        
      // check for left 
      } else if(value < current.value){
        // add left
        if(!current.left){ current.left = newNode; break; }
        
        current = current.left;
      } else {
        // if it's the same ignore
        break;
      }
    }
  }

  // search for a specific value
  contains(value){
    let current = this.root;

    while(current){
      if(current.value == value){
        return true;
      } else if (current.value > value){
        current = current.left;
      } else {
        current = current.right;
      }
    }

    return false;
  }
}

class DepthFirstTraverser extends BinarySearchTree {
  // pre-order -> root, left, right
  // in-order -> left, root, right
  // post-order -> left, right, root
  consstructor(){
    this.traverseMethod = 'pre-order';
  }

  setTraverseMethod(traverseMethod){
    if(traverseMethod == 'pre-order' || traverseMethod == 'in-order' || traverseMethod == 'post-order'){
      this.traverseMethod = traverseMethod;
    } else {
      console.error('Not a valid search method, must be "pre-order", "in-order" or "post-order"');
    }
  }

  getTraverseMethod(){
    return this.traverseMethod;
  }

  traverse(){
    switch(this.traverseMethod){
      case 'pre-order':
        this.preOrderTraverse(value);
        break;
      case 'in-order':
        this.inOrderTraverse(value);
        break;
      case 'post-order':
        this.postOrderTraverse(value);
        break;
      default:
        console.error('invalid traverse method');
    }
  }

  preOrderTraverse(value){


  }

  inOrderTraverse(value){

  }

  postOrderTraverse(value){

  }
}

class BreadthFirstTraverser extends BinarySearchTree {
  traverse(value){

  }
}

bst-recursive.js

// This Binary Search Tree is implemented using the prototypal pattern

var BinarySearchTree = function(value) {
  var instance = Object.create(BinarySearchTree.prototype);

    instance.value = value;
    // a BST where all values are higher than than the current value.
    instance.right = undefined;
    // a binary search tree (BST) where all values are lower than than the current value.
    instance.left = undefined;

  return instance
};

BinarySearchTree.prototype.insert = function (value) {
  // accepts a value and places in the tree in the correct position.
  var node = BinarySearchTree(value);

  function recurse(bst) {
    if (bst.value > value && bst.left === undefined) {
      bst.left = node;
    } else if (bst.value > value) {
      recurse(bst.left);
    } else if (bst.value < value && bst.right === undefined) {
      bst.right = node;
    } else if (bst.value < value) {
      recurse(bst.right);
    }
  }

  recurse(this);
}

BinarySearchTree.prototype.contains = function (value) {
  var doesContain = false;
  //accepts a value and returns a boolean reflecting whether or not the value is contained in the tree.
  function recurse(bst) {
    if (bst.value === value) {
      doesContain = true;;
    } else if (bst.left !== undefined && value < bst.value) {
      recurse(bst.left);
    } else if (bst.right !== undefined && value > bst.value) {
      recurse(bst.right)
    }
  }

  recurse(this);
  return doesContain;
}

BinarySearchTree.prototype.depthFirstLog = function (callback) {
  //accepts a callback and executes it on every value contained in the tree.
  function recurse(bst) {
    callback.call(bst, bst.value)

    if (bst.left !== undefined) {
      recurse(bst.left)
    }

    if (bst.right !== undefined) {
      recurse(bst.right);
    }
  }

  recurse(this);
}

pseudocode.md

Pseudocode

• Create BST constructor
  • define value, right child and left child
• Define insert method on prototype (value)
  • Create new node with passed in value
  • Create recursive function
    • If current node value > value && left child is undefined
      • Insert node as left child
    • If current node value > value
      • Recurse current node left child
    • If current node value <value && right child is undefined
      • Insert node as right child
    • If current node value <value
      • Recurse current node right child
  • Call recursive function on root node
• Define contains method on prototype (value)
  • Create variable to hold found node
  • Create recursive function
    • If current node value is equal to value
      • Set variable equal to true
    • else if BST left child is !undefined && value < BST value
      • recurse with current node's left child
    • else if BST right child is !undefined && value > BST value
      • recurse with current node's right child
  • Call recursive function on root node
  • Return variable of found node
• Define depthFirstLog method on prototype (callback)
  • Create recursive function
    • Use call with callback on BST and BST value
    • If left child is not undefined
      • Recurse through left child
    • If right child is not undefined
      • Recurse through right child
  • Call recursive function on root node