Return to Answer

##Observation

##Alternative

Observation

Alternative

This is to show that you made the code twice as long by simply adding the parent member to the class.

template<typename T>
class BST
{
 struct Node
 {
 Node* left;
 Node* right;
 T value;
 };
 Node* root = nullptr;
 // This function assumes node is not null.
 // So check before you call.
 Node* findLeftMostNode(Node* node) {
 return node->left == nullptr ? node: findLeftMostNode(node->left);
 }
 Node* insertNode(Node* node, T consT& val) {
 if (node == nullptr) {
 return new Node{nullptr, nullptr, val};
 }
 if (val < node->value) {
 node->left = insertNode(node->left, val);
 }
 else {
 node->right = insertNode(node->right, val);
 }
 return node;
 }
 Node* deleteNode(Node* node, T const& val)
 {
 if (node == nullptr) {
 return nullptr;
 }
 if (val < node->val) {
 node->left = deleteNode(node->left, val);
 }
 else if (val > node->val) {
 node->right = deleteNode(node->right, val);
 }
 else {
 // The interesting part.
 Node* old = nullptr; // the node to delete;
 if (node->left == nullptr) {
 old  = node;
 node = node->right; // the node to return as replacement
 }
 else if (node->right == nullptr) {
 old = node;
 node = node->left; // the node to return as replacement
 }
 else {
 // The shit just got real.
 // This is the complicated part.
 // Remember that both the left and right are not nullptr.
 // So the leftmost sub-node of the right tree is the smallest
 // value in the right subtree. 
 // If we move this value to here then the right sub-tree can
 // still be on the right of this node.
 Node* leftMost = findLeftMostNode(node->right);
 // Don't need to re-shape the tree simply move the value.
 node->val = leftMost->val;
 // We have moved the value.
 // But now we have to delete the value we just moved from the
 // right sub-tree. Luckily we have a function for that.
 node->right = deleteNode(node->right, leftMost->val);
 }
 delete old;
 }
 return node;
 }
 public:
 ~BST()
 {
 Node* bottomLeft = root == nullptr ? nullptr : findLeftMostNode(root);
 while (root) {
 Node* old = root;
 root = root->left;
 bottomLeft->left = old->right;
 bottomLeft = findLeftMostNode(bottomLeft);
 delete old;
 }
 }
 // Deletet the copy operator
 BST(BST const&) = delete;
 BST& operator(BST const&) = delete;
 // Simple interface.
 void insertNode(T const& val) {root = insertNode(root, val);}
 void deleteNode(T const& val) {root = deleteNode(root, val);}
}

template<typename T>
class BST
{
 struct Node
 {
 Node* left;
 Node* right;
 T value;
 };
 Node* root = nullptr;
 // This function assumes node is not null.
 // So check before you call.
 Node* findLeftMostNode(Node* node) {
 return node->left == nullptr ? node: findLeftMostNode(node->left);
 }
 Node* insertNode(Node* node, T consT& val) {
 if (node == nullptr) {
 return new Node{nullptr, nullptr, val};
 }
 if (val < node->value) {
 node->left = insertNode(node->left, val);
 }
 else {
 node->right = insertNode(node->right, val);
 }
 return node;
 }
 Node* deleteNode(Node* node, T const& val)
 {
 if (node == nullptr) {
 return nullptr;
 }
 if (val < node->val) {
 node->left = deleteNode(node->left, val);
 }
 else if (val > node->val) {
 node->right = deleteNode(node->right, val);
 }
 else {
 // The interesting part.
 Node* old = node; // the node to delete;
 // If both children are null.
 // Simply delete the node and return nullptr
 // as the value to be used for this point.
 if (node->left == nullptr && node->right == nullptr) {
 node = nullptr;
 }
 // If either the left or right node is null
 // then we can use the other one as the replacement for
 // for node in the tree.
 else if (node->left == nullptr) {
 node = node->right; // the node to return as replacement
 }
 else if (node->right == nullptr) {
 node = node->left; // the node to return as replacement
 }
 else {
 // The shit just got real.
 // We can't delete the node (as we can return two pointers)
 old = nullptr;

 // This is the complicated part.
 // Remember that both the left and right are not nullptr.
 // So the leftmost sub-node of the right tree is the smallest
 // value in the right subtree. 
 // If we move this value to here then the right sub-tree can
 // still be on the right of this node.
 Node* leftMost = findLeftMostNode(node->right);
 // Don't need to re-shape the tree simply move the value.
 node->val = leftMost->val;
 // We have moved the value.
 // But now we have to delete the value we just moved from the
 // right sub-tree. Luckily we have a function for that.
 node->right = deleteNode(node->right, leftMost->val);
 }
 delete old;
 }
 return node;
 }
 public:
 ~BST()
 {
 Node* bottomLeft = root == nullptr ? nullptr : findLeftMostNode(root);
 while (root) {
 Node* old = root;
 root = root->left;
 bottomLeft->left = old->right;
 bottomLeft = findLeftMostNode(bottomLeft);
 delete old;
 }
 }
 // Deletet the copy operator
 BST(BST const&) = delete;
 BST& operator(BST const&) = delete;
 // Simple interface.
 void insertNode(T const& val) {root = insertNode(root, val);}
 void deleteNode(T const& val) {root = deleteNode(root, val);}
}