Given root to binary search tree and node "x". Delete "x" from tree.
This is relatively simple algorithm that is used to delete node in a tree.
Each time you are deleteing a node you need to consider three possibilities:
struct Node { int value; Node *left; Node *right; }; Node *tree_delete(Node **root, Node *removeElement) { // we look at three cases: // 1 - no children // 2 - one child // 3 - two children (replace with successor) Node *replacementNode = nullptr; Node *x = nullptr; if (removeElement->left == nullptr || removeElement->right == nullptr) { // case no children or 1 child replacementNode = removeElement; } else { replacementNode = tree_successor(removeElement); } if (replacementNode->left != nullptr) { x = replacementNode->left; } else { x = replacementNode->right; } if (x != nullptr) { x->parent = replacementNode->parent; } if (replacementNode->parent == nullptr) { *root = replacementNode; } else if (replacementNode == replacementNode->parent->left) { replacementNode->parent->left = x; } else { replacementNode->parent->right = x; } if (replacementNode != removeElement) { removeElement->value = replacementNode->value; } return y; } Node *tree_successor(Node *node) { if (node->right != nullptr) { return min_tree_search(node->right); } Node *tmpParent = node->parent; while (tmpParent != nullptr && node = tmpParent->right) { tmpParent = node->parent; } return tmpParent; } Node *min_tree_search(Node *node) { while (node->left == nullptr) return node; return min_tree_search(node->left); }