binarysearchtree.js

function Node(value, parent, left, right) {
  this.value = value
  this.left = left || null
  this.right = right || null
  this.parent = parent || null
  this.height = () => {
    const lefth = this.left ? this.left.height() : -1
    const righth = this.right ? this.right.height() : -1
    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
  }
  this.insert = (value) => {
    if (value > this.value) {
      if (!this.right) {
        this.right = new Node(value, this)
        return this.right
      } else {
        return this.right.insert(value)
      }
    } else {
      if (!this.left) {
        this.left = new Node(value, this)
        return this.left
      } else {
        return this.left.insert(value)
      }
    }
  }
  this.find = (value) => {
    if (this.value == value) {
      return this
    }
    if (value > this.value) {
      if (!this.right) return null
      return this.right.find(value)
    } else {
      if (!this.left) return null
      return this.left.find(value)
    }
  }
  this.findMin = () => {
    if (!this.left) return this
    return this.left.findMin()
  }
}

function createBinaryTree(value) {
  let masterNode = new Node(value)
  const replaceChild = (parent, oldChild, newChild) => {
    if (!parent) {
      masterNode = newChild;
      if (masterNode !== null) {
        masterNode.parent = null
      }
    } else {
      if (parent.left === oldChild) {
        parent.left = newChild
      } else {
        parent.right = newChild
      }
      if (newChild) {
        newChild.parent = parent
      }
    }
  }
  const removeNode = (node) => {
    if (!node) return false
    if (node.left && node.right) {
      var min = node.right.findMin()
      var temp = node.value
      node.value = min.value
      min.value = temp
      return removeNode(min)
    } else {
      if (node.left) {
        replaceChild(node.parent, node, node.left)
      } else if (node.right) {
        replaceChild(node.parent, node, node.right)
      } else {
        replaceChild(node.parent, node, null)
      }
      return true
    }
  }
  return {
    getRoot: () => masterNode,
    insert: (value) => masterNode.insert(value),
    find: (value) => masterNode.find(value),
    removeNode
  }
}

const tree = createBinaryTree(50)
tree.insert(35)
tree.insert(40)
tree.insert(60)
tree.insert(55)
/*
Visual representation of tree:
    __50____
  35_      __60
     40  55
*/
console.log("Our initial tree", tree.getRoot())
console.assert(true == false, "Sanity check, this should fail")
console.assert(tree.find(35).value == 35, "did not find node with value 35")
console.assert(tree.find(50).left.value == 35, "35 was not left of 50")
console.assert(tree.find(35).right.value == 40, "40 was not right of 35")
console.assert(tree.find(60).parent.value == 50, "50 was not parent of value 60")

// check some heights
console.assert(tree.find(50).height() == 2, "the root node didnt have height of 2")

// remove root of tree
console.assert(tree.removeNode(tree.find(50)) == true, "Failed at removing root node value 50")
console.assert(tree.getRoot().value == 55, "new root value was not 55")

// remove node with value 40
console.assert(tree.removeNode(tree.find(40)) == true, "Failed at removing node value 40")
console.assert(tree.find(40) == null, "value 40 was found after removal")

console.log("Our tree after a few removals", tree.getRoot())
/*
Visual representation of tree after removals:
    __55__
  35      60
*/