Implementation of a binary search tree in JavaScript

javascript-bst.js

class Node {
  // stores given value and points to nothing
  constructor (value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

class Tree {
  // initially just has a root variable with null assigned
  constructor () {
    this.root = null
  }

  // helper functions

  // find node with minimum value in tree/subtree and return
  minNode = root => {
    // if no left child, root has to be min
    if (root.left === null) return root
    // else, look for min node in left subtree
    else this.minNode(root.left)
  }

  // starting from root, traverses through a tree/subtree and
  // inserts new node depending on its value
  traverseAndInsert = (root, node) => {
    // if new node value less than root
    if (node.value < root.value) {
      // if left node null, make new node the left node
      if (root.left === null) root.left = node
      // else get traverseAndInsert to find the correct place in left subtree to insert new node
      else this.traverseAndInsert(root.left, node)
     // if new node value greater than root
    } else {
      // if right node null, make new node the right node
      if (root.right === null) root.right = node
      // else get traverseAndInsert to find the correct place in right subtree to insert new node
      else this.traverseAndInsert(root.right, node)
    }
  }

  // starting from root, traverses through a tree/subtree and
  // deletes node with given value
  // and returns root of new tree/subtree with node removed
  traverseAndRemove = (root, value) => {
    // if root is null, return null
    if (root === null) return null

    // if value is less than root value, move to left subtree and remove from there
    if (value < root.value) {
      root.left = this.traverseAndRemove(root.left, value)
      return root
    // if value is greater than root value, move to right subtree and remove from there
    } else if (value > root.value) {
      root.right = this.traverseAndRemove(root.right, value)
      return root
    // if value is similar to root value
    } else {
      // if node has no kids, delete it
      if (root.left === null && root.right === null) {
        root = null
        return root // return null
      }

      // if has a left child only, assign left child to root
      if (root.right === null) {
        root = root.left
        return root
      }

      // if has a right child only, assign right child to root
      if (root.left === null) {
        root = root.right
        return root
      }

      // if has both children

      // get node with min value in right subtree
      let rightMin = this.minNode(root.right)
      // assign rightMin value to root
      root.value = rightMin.value

      // remove rightMin from right subtree
      root.right = this.traverseAndRemove(root.right, rightMin.value)

      return root
    }
  }

  // end of helper functions

  insert = value => {
    // create new node with given value
    let node = new Node(value)

    // if root null, make new node the root
    if (this.root === null) this.root = node
    // if not, get traverseAndInsert to find the correct place to insert new node
    else this.traverseAndInsert(this.root, node)
  }

  remove = value => {
    this.root = this.traverseAndRemove(this.root, value)
  }

  search = (root, value) => {
    // if root null, return null
    if (root === null) return null
    else {
      // if value less than root value, search in left subtree
      if (value < root.value) 
        return this.search(root.left, value)
      // if value greater than root value, search in right subtree
      else if (value > root.value) 
        return this.search(root.right, value)
      // if value similar to root value, return root
      else return root
    }
  }

  // left subtree -> root -> right subtree
  traverseInOrder = root => {
    if (root !== null) {
      this.traverseInOrder(root.left)
      console.log(root.value)
      this.traverseInOrder(root.right)
    }
  }
}

// test

// let tree = new Tree()

// tree.insert(7)
// tree.insert(24)
// tree.insert(9)
// tree.insert(36)
// tree.insert(21)

// console.log(tree.root)

// tree.traverseInOrder(tree.root)

// tree.remove(7)
// tree.traverseInOrder(tree.root)

// tree.remove(21)
// tree.traverseInOrder(tree.root)

// tree.remove(24)
// tree.traverseInOrder(tree.root)

// console.log(tree.search(tree.root, 8))
// console.log(tree.search(tree.root, 36))