Binary Search Tree (BST)

binarySearchTree.js

function BinarySearchTree (rootData) {
  this.root = null;
  this.nodes = 0;
  this.add(rootData);
}

BinarySearchTree.prototype = {
  constructor : BinarySearchTree,
  add : function add (data) {
    if (this.root === null) {
      this.root = new BSTNode();
    }
    this.root.addNode(data);
    this.nodes++;
  },
  addAll : function addAll (array) {
    for (var i = 0; i < array.length; i++){
      this.add(array[i]);
    }
  },
  find : function (data) {
    var temp = this.root;
    while (temp !== null && temp.data !== data) {
      if (data < temp.data) {
        temp = temp.left;
      } else if (data > temp.data) {
        temp = temp.right;
      }
    }
    return temp;
  },
  findHeight : function () {
    return this.root.findHeight();
  }
};

function BSTNode (data) {
  if (typeof data !== 'undefined') {
    this.data = data;
  }
}

BSTNode.prototype = {
  constructor : BSTNode,
  data : null,
  left : null,
  right : null,
  addNode : function addNode (data) {
    if (typeof data !== 'undefined' && (typeof this.data === 'undefined' || this.data === null)) {
      this.data = data;
      return true;
    } else if (data <= this.data) {
      if (this.left === null) {
        this.left = new BSTNode();
      }
      this.left.addNode(data);
    } else if (data > this.data) {
      if (this.right === null) {
        this.right = new BSTNode();
      }
      this.right.addNode(data);
    } else {
      return false;
    }
  },
  findHeight : function findHeight () {
    var left, right;
    if (this.left === null && this.right === null) {
      return 0;
    } else {
      left = this.left !== null ? this.left.findHeight() : 0;
      right = this.right !== null ? this.right.findHeight() : 0;
      return (Math.max(left, right) + 1);
    }
  },
  // breadthTraverse - Level-order traversal
  breadthTraverse : function breadthTraverse () {
    var queue = [], tempArr = [], tempNode;
    queue.push(this);
    while (queue.length > 0) {
      tempNode = queue.shift();
      tempArr.push(tempNode.data);
      if (tempNode.left !== null) {
        queue.push(tempNode.left);
      }
      if (tempNode.right !== null) {
        queue.push(tempNode.right);
      }
    }
    return tempArr;
  },
  // depthTraverse - traverse as far as possible along each branch before backtracking
  // 
  // preOrPostOrInorder = undefined or not Bool - Inorder traversal <left><root><right>
  // preOrPostOrInorder = true - Preorder traversal <root><left><right>
  // preOrPostOrInorder = false - Postorder traversal <left><right><root>
  depthTraverse : function depthTraverse (preOrPostorder) {
    var tempArr = [];
    switch (preOrPostorder) {
      case true:
        tempArr = tempArr.concat(this.data);
        if (this.left !== null) {
          tempArr = tempArr.concat(this.left.depthTraverse(preOrPostorder));
        }
        if (this.right !== null) {
          tempArr = tempArr.concat(this.right.depthTraverse(preOrPostorder));
        }
        break;
      case false:
        if (this.left !== null) {
          tempArr = tempArr.concat(this.left.depthTraverse(preOrPostorder));
        }
        if (this.right !== null) {
          tempArr = tempArr.concat(this.right.depthTraverse(preOrPostorder));
        }
        tempArr = tempArr.concat(this.data);
        break;
      default:
        if (this.left !== null) {
          tempArr = tempArr.concat(this.left.depthTraverse(preOrPostorder));
        }
        tempArr = tempArr.concat(this.data);
        if (this.right !== null) {
          tempArr = tempArr.concat(this.right.depthTraverse(preOrPostorder));
        }
        break;
    }
    return tempArr;
  },
  isBST : function isBST (min, max) {
    min = typeof min !== 'undefined' ? min : -Infinity;
    max = typeof max !== 'undefined' ? max : Infinity;
    if (this.data >= min && this.data < max) {
      if ( ((this.left !== null && this.left.isBST(min, this.data)) || this.left === null) &&
           ((this.right !== null && this.right.isBST(this.data, max)) || this.right === null) ) {
        return true;
      } else {
        return false;
      }
    } else {
      return false;
    }
  }
};