I trying to see if I implemented these operations correctly and if they could be optimized in any way. The implementations are just the typical implementations found online but I adjusted them to work with pointers. I did not find pseudocode for transplant, it was only described and I am unsure if it does what it is supposed to do. The tree works correctly for my small test cases, but I have not tried it with bigger data sets and operations. I purposely made the tree non-owning but if it were owning, left and right children could be unique_ptr's and parent be a Node*. I may implement that later.

class Node {

public:

  Node(int key) : key(key) {}

  Node* parent = nullptr;

  Node* left = nullptr;

  Node* right = nullptr;

  int key;

};



class BinarySearchTree {

public:

  BinarySearchTree() = default;

  /// create tree from existing nodes

  BinarySearchTree(Node* nodes, unsigned n);

  /// insert key into tree

  void insert(Node* node);

  /// remove node with key

  void remove(Node* node);

  /// find smallest node in subtree

  Node* minimum(Node* node) const;

  /// find largest node in subtree

  Node* maximum(Node* node) const;

  /// find successor of node

  Node* successor(Node* node) const;

  /// find predecessor of node

  Node* predecessor(Node* node) const;

  /// replace subtree at a with subtree at b

  void transplant(Node* a, Node* b);

  /// find node with key

  Node* find(int key) const;

  /// find kth smallest element

  Node* kth(unsigned k) const;

  /// write data to stream

  friend std::ostream& operator<<(std::ostream& out, const BinarySearchTree& tree);



private:

  /// helper method to initialize tree

  void build_bst(BinarySearchTree& tree, Node* nodes, unsigned n);

  /// helper method for find

  Node* find(int key, Node* subtree) const;

  /// pointer to the root

  Node* root = nullptr;

};



void BinarySearchTree::build_bst(BinarySearchTree& tree, Node* nodes, unsigned n) {

  if (n == 0) return;

  tree.insert(nodes[n/2]);

  build_bst(tree, nodes, n/2);

  build_bst(tree, nodes + n/2 + 1, n - 1 - n/2);

}



BinarySearchTree::BinarySearchTree(Node* nodes, unsigned n) {

  build_bst(*this, nodes, n);

}



void BinarySearchTree::insert(Node* node) {

  Node* parent = nullptr;

  Node* child = root;



  while (child) {

    parent = child;

    if (node->key < child->key)

      child = child->left;

    else

      child = child->right;

  }



  node->parent = parent;

  if (!parent) {

    root = node;

  } else if (node->key < parent->key) {

    parent->left = node;

  } else {

    parent->right = node;

  }

}



void BinarySearchTree::remove(Node* node) {

  if (!node->left && !node->right) {

    // special case where only node is root

    if (node->parent) {

    // remove leaf node      

      if (node->parent->key < node->key) {

        node->parent->right = nullptr;

      } else {

        node->parent->left = nullptr;

      }

    } else {

      root = nullptr;

    }

    node->parent = nullptr;

  } else if (!node->left && node->right) {

    // no left child

    transplant(node, node->right);

  } else if (node->left && !node->right) {

    // no right child

    transplant(node, node->left);

  } else {

    // check if min = successor(node)

    Node* min = successor(node);

    if (min->parent != node) {

      transplant(min, min->right);

      min->right = node->right;

      min->right->parent = min;

    }

    transplant(node, min);

    min->left = node->left;

    min->left->parent = min;

  }

}



Node* BinarySearchTree::minimum(Node* node) const {

  Node* parent = nullptr;

  Node* child = node;



  while (child) {

    parent = child;

    child = child->left;

  }



  return parent;

}



Node* BinarySearchTree::maximum(Node* node) const {

  Node* parent = nullptr;

  Node* child = node;



  while (child) {

    parent = child;

    child = child->right;

  }



  return parent;

}



Node* BinarySearchTree::successor(Node* node) const {

  if (node->right) {

    // find minimum of right subtree

    return minimum(node->right);

  } else {

    // find parent of furthest node through right branches

    Node* iter = node;

    while (iter->parent) {

      if (iter->parent->key < iter->key) {

        iter = iter->parent;

      } else {

        break;

      }

    }



    // will return nullptr if no successor

    return iter->parent;

  }

}



Node* BinarySearchTree::predecessor(Node* node) const {

  if (node->left) {

    return maximum(node->left);

  } else {

    // find parent of furthest node through left branches

    Node* iter = node;

    while (iter->parent) {

      if (iter->key < iter->parent->key) {

        iter = iter->parent;

      } else {

        break;

      }

    }



    // will return nullptr if no predecessor exists

    return iter->parent;

  }

}



void BinarySearchTree::transplant(Node* a, Node* b) {

  if (b->parent->key < b->key) {

    b->parent->right = nullptr;

  } else {

    b->parent->left = nullptr;

  }



  b->parent = a->parent;



  // special case when a is root

  if (a->parent) {

    if (a->parent->key < a->key) {

      a->parent->right = b;

    } else {

      a->parent->left = b;

    }

  } else {

    root = b;

  }

}



Node* BinarySearchTree::find(int key) const {

  return find(key, root);

}



Node* BinarySearchTree::find(int key, Node* subtree) const {

  if (!subtree) return nullptr;

  if (subtree->key < key)

    return find(key, subtree->right);

  else if (subtree->key > key)

    return find(key, subtree->left);

  else

    return subtree;

}



Node* BinarySearchTree::kth(unsigned k) const {

  Node* kth = minimum(root);

  for (unsigned i = 0; i < k-1; ++i) {

    if (kth)

      kth = successor(kth);

    else

      return kth;

  }



  // returns nullptr if kth element does not exist

  return kth;

}



/// in-order traversal/print

std::ostream& operator<<(std::ostream& out, const Node& node) {

  if (node.left)

    out << *node.left;

  out << node.key << ' ';

  if (node.right)

    out << *node.right;

  return out;

}



/// print the entire tree

std::ostream& operator<<(std::ostream& out, const BinarySearchTree& tree) {

  if (!tree.root) return out;

  return out << *tree.root;

}

Good stuff

• Consistent indentation


• 
  /// documenting comments (I applaud to that)


• What it does first, how it does it last
  (although I personally prefer inline bodies, this is nice example of the separation being done right)
  

Design

What could be the reason to have the nodes exposed and not owned?
The tree should, in my opinion, accept and expose only values and be a template:

template<class T>

class BinarySearchTree {

    struct Node {

        std::unique_ptr<Node> left = nullptr;

        std::unique_ptr<Node> right = nullptr;

        T key;

        Node(T key) : key(std::move(key)) {}

    };

public:

    BinarySearchTree(std::initializer_list<T> init);

You should notice that:

1. It uses std::unique_ptr because there is simply no excuse now! If you, for whatever reason, need something like Node* then it should rather be iterator or node handle (C++17).


2. It has constructor accepting std::initializer_list to enable construction like BinarySearchTree<int>{1,2,3}
   


3. No parent inside node. I will elaborate this a bit more:

I can understand why you did this, because I have done it during my first exam and it was not received well by the teacher. You can use stacks tracking the path from root to current node (maybe make it part of the iterator if needed) to implement every exposed operation. I know it is easier to have the parent in the node, but it should not be there.

Balancing the tree

You have provided constructor (BinarySearchTree(Node* nodes, unsigned n) using build_bst(BinarySearchTree& tree, Node* nodes, unsigned n)) that will produce well-balanced tree if the input array is sorted (should probably check and sort if needed), but did not make the tree read-only, which means, that you should provide some means of rebalancing the tree. Try reading about Red-Black Tree (and maybe AVL Tree as alternative).

Personal story: The purpose of the exam was to show understanding of pointers to handle joining two trees or heaps. The teacher could not imagine that somebody would even think about optimal solution... ehm, I did, and received some unwanted attention for the rest of my studies for doing so while helping myself using that parent pointer instead of three stacks - there was simply not enough time to pull this out... and I was not supposed to even think about such solution, you know :D I hope you now understand that I am not stressing the removal of parent too much :)