BST deletion has three cases: deleting a leaf (trivial), deleting a node with one child (replace with child), and deleting a node with two children (replace with in-order successor or predecessor). The two-children case is the tricky one and requires finding the minimum of the right subtree.
Node* minNode(Node* root) { while(root->left) root=root->left; return root; }
Node* deleteNode(Node* root, int val) {
if (!root) return nullptr;
if (val < root->val) root->left = deleteNode(root->left, val);
else if (val > root->val) root->right = deleteNode(root->right, val);
else {
if (!root->left) { Node* t=root->right; delete root; return t; }
if (!root->right) { Node* t=root->left; delete root; return t; }
Node* succ = minNode(root->right);
root->val = succ->val;
root->right = deleteNode(root->right, succ->val);
}
return root;
}Case 1: Leaf node — simply remove it. Case 2: One child — replace the node with its child. Case 3: Two children — find the in-order successor (smallest value in right subtree), copy its value here, then delete the successor.
The in-order successor of a node is the smallest value greater than it — the leftmost node in the right subtree. Using it for deletion ensures the BST property is maintained after the swap.
The recursive delete function returns the (possibly new) root of each subtree. This elegant approach handles all three cases uniformly: update root.left or root.right with the return value.
Quiz coming soon for this algorithm.