functional-binary-trees.js

class BinaryTree {}

class EmptyBinaryTree extends BinaryTree {
  isEmpty () { return true }
  depth () { return 0 }
  count () { return 0 }
  inorder (fn) {}
  preorder (fn) {}
  postorder (fn) {}
  contains (x) { return false }
  insert (x) { return new BinaryTreeNode(x) }
  remove (x) { return this }
}

const emptyTree = new EmptyBinaryTree()

class BinaryTreeNode extends BinaryTree {
  constructor (
    value,
    left = emptyTree,
    right = emptyTree
  ) {
    super()

    this.value = value
    this.left = left
    this.right = right
  }

  isEmpty () { return false }

  depth () {
    return 1 + Math.max(
      this.left.depth(),
      this.right.depth()
    )
  }

  count () {
    return 1 + this.left.count() + this.right.count()
  }

  inorder (fn) {
    this.left.inorder(fn)
    fn(this.value)
    this.right.inorder(fn)
  }

  preorder (fn) {
    fn(this.value)
    this.left.preorder(fn)
    this.right.preorder(fn)
  }

  postorder (fn) {
    this.left.postorder(fn)
    this.right.postorder(fn)
    fn(this.value)
  }

  contains (x) {
    return x === this.value ||
      (x < this.value && this.left.contains(x)) ||
      (x > this.value && this.right.contains(x))
  }

  insert (x) {
    return new BinaryTreeNode(
      this.value,
      x < this.value
        ? this.left.insert(x)
        : this.left,
      x >= this.value
        ? this.right.insert(x)
        : this.right
    )
  }

  remove (x) {
    if (x === this.value) {
      const leftEmpty = this.left.isEmpty()
      const rightEmpty = this.right.isEmpty()

      if (leftEmpty && rightEmpty) {
        return emptyTree
      }

      if (leftEmpty) {
        return this.right
      }

      if (rightEmpty) {
        return this.left
      }

      return new BinaryTreeNode(this.right.value, this.left)
    }

    if (this.contains(x)) {
      return new BinaryTreeNode(
        this.value,
        x < this.value
          ? this.left.remove(x)
          : this.left,
        x > this.value
          ? this.right.remove(x)
          : this.right
      )
    }

    return this
  }
}