index.js

/* eslint-disable consistent-return */
const Node = require('./Node');

class BinarySearchTree {
  constructor(value) {
    this.root = new Node(value);
  }

  insert(root, value) {
    if (root === null) {
      const newNode = new Node(value);
      // eslint-disable-next-line no-param-reassign
      root = newNode;
      return root;
    }

    if (value < root.value) {
      // eslint-disable-next-line no-param-reassign
      root.leftChild = this.insert(root.leftChild, value);
      return root;
    }
    if (value > root.value) {
      // eslint-disable-next-line no-param-reassign
      root.rightChild = this.insert(root.rightChild, value);
      return root;
    }
  }

  preorder(root) {
    /** returning an array so as to make testing easy */
    let arr = [];
    if (root === null) return [];
    arr.push(root.value);

    const left = this.preorder(root.leftChild);
    arr = [...arr, ...left];

    const right = this.preorder(root.rightChild);
    arr = [...arr, ...right];
    return arr;
  }

  inorder(root) {
    /** left - root - right */
    if (root === null) return [];
    let arr = [];
    const left = this.inorder(root.leftChild);
    arr = [...left, ...arr];

    // print root
    arr = [...arr, root.value];

    const right = this.inorder(root.rightChild);
    arr = [...arr, ...right];
    return arr;
  }

  postorder(root) {
    /** left - right - root */

    if (root === null) return [];
    let arr = [];

    const left = this.postorder(root.leftChild);
    arr = [...left, ...arr];

    const right = this.postorder(root.rightChild);
    arr = [...arr, ...right];

    return [...arr, root.value];
  }

  search(root, value) {
    if (root === null) return false;
    if (value === root.value) return true;

    if (value < root.value) {
      return this.search(root.leftChild, value);
    }
    if (value > root.value) {
      return this.search(root.rightChild, value);
    }
  }

  delete(root, value) {
    if (root === null) {
      return root;
    }

    if (value > root.value) {
      // eslint-disable-next-line no-param-reassign
      root.rightChild = this.delete(root.rightChild, value);
    } else if (value < root.value) {
      // eslint-disable-next-line no-param-reassign
      root.leftChild = this.delete(root.leftChild, value);
    } else {
      // found the node
      if (root.leftChild === null) {
        // there is a right sub-tree
        return root.rightChild;
      }
      if (root.rightChild === null) {
        // there is a left sub-tree
        return root.leftChild;
      }
      /**
       * the root contain 2 childs, we got 2 options:
       * 1. We can either find the Node with minimum value at from the right sub-tree
       * 2. Or, we can find the Node with maximum value from the left sub-tree
       *
       * I'm picking up 1 here
       */
      const minRightNode = this.findMinNode(root.rightChild);
      // eslint-disable-next-line no-param-reassign
      root.value = minRightNode.value;
      // eslint-disable-next-line no-param-reassign
      root.rightChild = this.delete(root.rightChild, minRightNode.value);
      return root;
    }
    return root;
  }

  findMinNode(root) {
    /** The minnimum values is the let most leaf node in BST */
    if (root.leftChild === null) return root;
    return this.findMinNode(root.leftChild);
  }

  findMaxNode(root) {
    if (root.rightChild === null) return root;
    return this.findMaxNode(root.rightChild);
  }

  isEmpty() {
    return this.root === null;
  }

  /** Layered methods to simplify the BST API  */

  add(value) {
    return this.insert(this.root, value);
  }

  traversePreorder() {
    return this.preorder(this.root);
  }

  traversePostorder() {
    return this.postorder(this.root);
  }

  traverseInorder() {
    return this.inorder(this.root);
  }

  searchFor(value) {
    return this.search(this.root, value);
  }

  getMinimum() {
    const minNode = this.findMinNode(this.root);
    return minNode.value;
  }

  getMaximum() {
    const maxNode = this.findMaxNode(this.root);
    return maxNode.value;
  }

  remove(value) {
    this.root = this.delete(this.root, value);
  }
}

// const bst = new BinarySearchTree(6);
// console.log(bst.root);
// bst.add(4);
// bst.add(9);
// bst.add(2);
// bst.add(5);
// bst.add(8);
// bst.add(12);

// console.log(bst.root);

// const preorder = bst.traversePreorder();
// console.log('Preorder Traversal - ', preorder);

// const inorder = bst.traverseInorder();
// console.log('Inorder Traversal - ', inorder);

// const postorder = bst.traversePostorder();
// console.log('Postorder Traversal - ', postorder);

// const search = 18;
// console.log(`Search for ${search}`, bst.searchFor(search));

// const minNode = bst.getMinimum();
// console.log('Minimum value =>', minNode);

// const maxNode = bst.getMaximum();
// console.log('Maximum value =>', maxNode);

// bst.remove(4);
// console.log(bst.traversePreorder());

// console.log(bst.root);

module.exports = BinarySearchTree;