bstdelete.cpp

bool remove(T d) {
    if (!contains(d))
      return false;
    removeHelper(root_, d);
    return true;
  }

  TreeNode<T>* removeHelper(TreeNode<T> *n, T d) {
    if (d < n->data_) {
      n->left_ = removeHelper(n->left_, d);
    } else if (d > n->data_) {
      n->right_ = removeHelper(n->right_, d);
    } else {
      if (n->left_ == nullptr && n->right_ == nullptr) { // no children
        delete n;
        return nullptr;
      } else if (n->left_ == nullptr) { // has right child
        TreeNode<T> *rightchild = n->right_;
        delete n;
        return rightchild;
      } else if (n->right_ == nullptr) { // has left child
        TreeNode<T> *leftchild = n->left_;
        delete n;
        return leftchild;
      } else { // 2 children
        TreeNode<T> *predecessor = findPredecessor(n);
        std::swap(n->data_, predecessor->data_);
        n->left_ = removeHelper(n->left_, d);
      }
    }
    return n;
  }

  TreeNode<T>* findPredecessor(TreeNode<T> *n) {
    TreeNode<T> *p = n->left_;
    while (p->right_ != nullptr)
      p = p->right_;    
    return p;
  }