JS Data Structures: Trees, see more at: https://medium.com/p/5dee18f68982

DATA_STRUCTURES_BSTImplementation.js

function BST() {
  let root = null

  class Utils {
    static node(key) {
      return { key, left: null, right: null }
    }

    static insertNode(node, key) {
      if (!node) {
        return Utils.node(key)
      }

      if (node.key !== key) {
        const nextPosition = node.key > key ? 'left' : 'right'

        node[nextPosition] = Utils.insertNode(node[nextPosition], key)
      }

      return node
    }

    static statusNode(node) {
      return {
        LEAF: node.left === null && node.right === null,
        TWO_CHILDREN: node.left !== null && node.right !== null,
        ONE_CHILD:
          (node.right === null && node.left !== null) ||
          (node.left === null && node.right !== null),
      }
    }

    static removeNode(node, key) {
      if (node && node.key === key) {
        const isNode = Utils.statusNode(node)

        if (isNode.LEAF) {
          return null
        }

        if (isNode.TWO_CHILDREN) {
          const minKeyRight = Utils.minNode(node.right)
          node.key = minKeyRight
          node.right = Utils.removeNode(node.right, minKeyRight)
        }

        if (isNode.ONE_CHILD) {
          const position = node.key > key ? 'left' : 'right'
          node.key = node[position].key
          node[position] = Utils.removeNode(node[position], node.key)
        }
      }

      if (node && node.key !== key) {
        const nextPosition = node.key > key ? 'left' : 'right'

        node[nextPosition] = Utils.removeNode(node[nextPosition], key)
      }

      return node
    }

    static minNode(node) {
      if (!node) {
        return null
      }

      return node.left ? Utils.minNode(node.left) : node.key
    }

    static maxNode(node) {
      if (!node) {
        return null
      }

      return node.right ? Utils.maxNode(node.right) : node.key
    }
  }

  class PublicBST {
    insert(key) {
      root = Utils.insertNode(root, key)
    }

    remove(key) {
      root = Utils.removeNode(root, key)
    }

    has(key, node = root) {
      if (!node) {
        return false
      }

      const nextPosition = node.key > key ? 'left' : 'right'

      return node.key === key ? true : this.has(key, node[nextPosition])
    }

    min() {
      return Utils.minNode(root)
    }

    max() {
      return Utils.maxNode(root)
    }

    inOrderTraverse(callback, node = root) {
      if (node) {
        this.inOrderTraverse(callback, node.left)
        callback(node)
        this.inOrderTraverse(callback, node.right)
      }
    }

    inPreOrderTraverse(callback, node = root) {
      if (node) {
        callback(node)
        this.inPreOrderTraverse(callback, node.left)
        this.inPreOrderTraverse(callback, node.right)
      }
    }

    inPostOrderTraverse(callback, node = root) {
      if (node) {
        this.inPostOrderTraverse(callback, node.left)
        this.inPostOrderTraverse(callback, node.right)
        callback(node)
      }
    }
  }

  return new PublicBST()
}