Binary Search Tree Implementation with JavaScript

js-binary-search-tree-impl.js

// https://www.youtube.com/watch?v=gcULXE7ViZw
// TreeHouse: delete node : https://www.youtube.com/watch?v=5cU1ILGy6dM

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

  class BinarySearchTree {
    constructor(){
      this.root = null;
    }
    insert(value){
      const newNode = new Node(value);

      if(this._isEmpty()) {
          this.root = newNode;
          return this;
      }
      
      let currentNode = this.root;
      let direction;
      let canTraverse; 
      while(true) {
          direction = value > currentNode.value ? "right" : "left";
          canTraverse = currentNode[direction] != null;
          if (canTraverse) {
              currentNode = currentNode[direction];
          } else {
              currentNode[direction] = newNode;
              return this;
          }
      }
    }

    lookup(value){

      if(this._isEmpty()) {
          return null;
      }

      let currentNode = this.root;
      let direction;
      let canTraverse; 

      while(true) {
          if (currentNode.value === value) {
              return currentNode;
          }

          direction = value > currentNode.value ? "right" : "left";
          canTraverse = currentNode[direction] != null;
          if (canTraverse) {
            currentNode = currentNode[direction];
          } else {
            return null;
          }
      }
    }

    _getMinNode(node) {
      if (node) {
        while(node.left) {
          node = node.left;
        }
        return node;
      }
    }

    _getMaxNode(node) {
      if (node) {
        while(node.right) {
          node = node.right;
        }
        return node;
      }
    }


    _isEmpty() {
        return this.root === null;
    }
    
    _removeNode (root, value) {
      if (!root) {
        return null;
      }
      let currentNode = root;
      
      if (currentNode.value === value) {
        let isLeafNode = !currentNode.left && !currentNode.right;
        let hasOnlyRightChild = currentNode.left === null && currentNode.right !== null;
        let hasOnlyLeftChild = currentNode.left !== null && currentNode.right === null;


        if (isLeafNode) {
          return null;
        }
        
        if (hasOnlyRightChild) {
          return currentNode.right;
        }

        if (hasOnlyLeftChild) {
          return currentNode.left;
        }
        
        var minNode = this._getMinNode(currentNode.right);
        currentNode.value = minNode.value;
        currentNode.right = this._removeNode(currentNode.right, minNode.value);
        return currentNode;
      } else {
        if (value > currentNode.value) {
          currentNode.right = this._removeNode(currentNode.right, value)
          return currentNode;
        } else if (value < currentNode.value) {
          currentNode.left = this._removeNode(currentNode.left, value);
          return currentNode;
        }
        else {
          return null;
        }
      }
    }
    remove (value) {
      this.root = this._removeNode(this.root, value);
    }
  }

  function traverse(node) {
      const tree = { value: node.value };
      tree.left = node.left === null ? null : traverse(node.left);
      tree.right = node.right === null ? null : traverse(node.right);
      return tree;
    }

  const tree = new BinarySearchTree();
  tree.insert(9)
  tree.insert(4)
  tree.insert(6)
  tree.insert(20)
  tree.insert(170)
  tree.insert(15)
  tree.insert(1)

  //     9
  //  4     20
  //1  6  15  170
  
  debugger;
  tree.remove(9);
//     15
//  4     20
//1  6      170
  
  debugger;
  tree.remove(20);
//     15
//  4     170
//1  6     
  debugger;
  tree.remove(4);
//     15
//  6     170
//1       
  debugger;