const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
}

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}

class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
  toString() {
    return `${this.key}`
  }
}


class BinarySearchTree {
  constructor (compareFn = defaultCompare) {
    this.compareFn = compareFn  // 比较节点值
    this.root = null            // Node 类型的根节点
  }

  insertNode (node, key) {
    // 如果待插入的节点的 key，比当前节点的 key 小，则往节点的左边插入
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      // 如果该节点的左边恰好为 空
      if (node.left == null) {
        node.left = new Node(key)
      } else {
        this.insertNode(node.left, key)
      }
    // 否则往节点的右边插入
    } else {
      // 如果该节点的右边恰好为 空
      if (node.left == null) {
        node.right = new Node(key)
      } else {
        this.insertNode(node.right, key)
      }
    }
  }
  insert (key) {
    if (this.root == null) {
      this.root = new Node(key)
    } else {
      this.insertNode(this.root, key)
    }
  }
  searchNode (node, key) {
    if (node == null) return false
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      return this.searchNode(node.left, key)
    } else if (this.compareFn(key, node.key) === Compare.Bigger_THAN) {
      return this.searchNode(node.right, key)
    } else {
      return true
    }
  }
  search (key) {
    return this.searchNode(this.root, key)
  }
  inOrderTraverseNode (node, callback) {
    if (node != null) {
      this.inOrderTraverseNode(node.left, callback)
      callback(node.key)
      this.inOrderTraverseNode(node.right, callback)
    }
  }
  preOrderTraverseNode (node, callback) {
    if (node != null) {
      callback(node.key)
      this.preOrderTraverseNode(node.left, callback)
      this.preOrderTraverseNode(node.right, callback)
    }
  }
  postOrderTraverseNode (node, callback) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback)
      this.postOrderTraverseNode(node.right, callback)
      callback(node.key)
    }
  }
  // 中序遍历
  inOrderTraverse (callback) {
    this.inOrderTraverseNode(node, callback)
  }
  // 前序遍历
  preOrderTraverse (callback) {
    this.preOrderTraverseNode(node, callback)
  }
  // 后序遍历
  postOrderTraverse (callback) {
    this.postOrderTraverseNode(node, callback)
  }
  minNode (node) {
    let current = node
    while (current != null && current.left != null) {
      current = current.left
    }
    return current
  }
  min () {
    return this.minNode(this.root)
  }
  maxNode (node) {
    let current = node
    while (current != null && current.right != null) {
      current = current.right
    }
    return current
  }
  max () {
    return this.maxNode(this.root)
  }
  removeNode (node, key) {
    if (node == null) return null
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.left, key)
      return node
    } else if (this.compareFn(key, node.key) === Compare.Bigger_THAN) {
      node.right = this.removeNode(node.right, key)
      return node
    } else {
      // 如果该节点是叶子节点，直接删除
      if (node.left == null && node.right == null) {
        node = null
        return node
      }
      // 左子树为空
      if (node.left == null) {
        node = node.right
        return node
      } else if (node.right == null) {
        // 右子树为空
        node = node.left
        return node
      }
      // 左右子树都不为空
      const aux = this.minNode(node.right)
      node.key = aux.key
      node.right = this.removeNode(node.right, aux.key)
    }

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

}