class Node {
 constructor(key) {
  this.key = key;
  this.left = null;
  this.right = null;
 }
}

class Tree{
 constructor(param = null) {
  if (param) {
   this.root = new Node(param);
  } else {
   this.root = null;
  }
 }
}

insert(key) {
 if (this.root === null) {
  this.root = new Node(key);
 } else {
  this._insertNode(this.root, key);
 }
}
_insertNode(node, key) {
 if (key < node.key) {
  if (node.left === null) {
   node.left = new Node(key);{1}
  } else {
   this._insertNode(node.left, key);{2}
  }
 } else if (key > node.key) {
  if (node.right === null) {
   node.right = new Node(key);{3}
  } else {
   this._insertNode(node.right, key);{4}
  }
 }
}

inOrderTraverse(callback) {
 this._inOrderTraverse(this.root, callback);
}
_inOrderTraverse(node, callback) {
 if (node) {
  this._inOrderTraverse(node.left, callback);
  callback(node.key);
  this._inOrderTraverse(node.right, callback);
 }
}

search(value) {
 if (this.root) {
  if (value === this.root.key) {
   return true;
  } else {
   return this._searchNode(value, this.root);
  }
 }
 throw new Error('this.root 不存在');
}
_searchNode(value, node) {
 if (!node) {
  return false;
 }
 if (value === node.key) {
  return true;
 }
 if (value > node.key) {
  return this._searchNode(value, node.right);
 } else if (value < node.key) {
  return this._searchNode(value, node.left);
 }
}

remove(key) {
 this._removeNode(this.root, key);
}
_removeNode(node, value) {
 if (!node) {
  return null;
 }
 if (value > node.key) {
  node.right = this._removeNode(node.right, value);
 } else if (value < node.key) {
  node.left = this._removeNode(node.left, value);
 } else {
  // 如果没有左子树，那么将右子树根节点作为替换节点
  if (!node.left) {
   return node.right;
   // 如果存在左子树，那么取右子树最小节点作为替换节点
  } else if (node.left) {
   return this._minNode(node.right);
  }
 }
}