BinarySearchTree.js

// tree node
class TreeNode {
  constructor(value) {
    this.value = value
    this.parent = null
    this.left = this.right = null
  }
  insert(newNode) {
    const {
      value
    } = newNode
    if (value === this.value) {
      return
    }
    if (value > this.value) {
      if (!this.right) {
        this.right = newNode
        newNode.parent = this
      } else {
        this.right.insert(newNode)
      }
    } else {
      if (!this.left) {
        this.left = newNode
        newNode.parent = this
      } else {
        this.left.insert(newNode)
      }
    }
  }
  traverse() {
    if (this.left) {
      this.left.traverse()
    }
    console.log(this.value)
    if (this.right) {
      this.right.traverse()
    }
  }
  find(v) {
    if (this.value === v) {
      return this
    }
    if (v > this.value) {
      return this.right ? this.right.find(v) : null
    } else {
      return this.left ? this.left.find(v) : null
    }
  }
  findMin() {
    if (!this.left) {
      return this
    }
    return this.left.findMin()
  }
  remove(v) {
    const {
      value
    } = this
    if (v > value) {
      this.right = this.right ? this.right.remove(v) : null
      return this
    } else if (v < value) {
      this.left = this.left ? this.left.remove(v) : null
      return this
    } else {
      if (!this.left && !this.right) { // leaf
        return null
      } else if (this.left && this.right) { // 2 child
        const minRightNode = this.right.findMin()
        const newValue = minRightNode.value
        const newRight = this.right.remove(newValue)
        this.right = newRight
        this.value = newValue
        return this
      } else { //single child
        const child = this.left || this.right
        child.parent = this.parent
        return child
      }
    }
  }

}
// BinarySearchTree
class BinarySearchTree {
  constructor() {
    this.root = null
  }
  insert(newNode) {
    if (!this.root) {
      this.root = newNode
    }
    this.root.insert(newNode)
  }
  traverse() {
    if (!this.root) {
      return
    }
    this.root.traverse()
  }
  find(v) {
    if (!this.root) {
      return null
    }
    return this.root.find(v)
  }
  remove(v) {
    if (!this.root) {
      return
    }
    this.root = this.root.remove(v)
  }
}