Deletion in a Binary Search Tree (BST) involves removing a node while maintaining the BST properties. There are three cases to handle:
1. Leaf Node: Simply remove the node as it has no children.
2. Node with One Child: Remove the node and link its parent directly to its child.
3. Node with Two Children: Find the node’s in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree). Replace the node’s value with the successor/predecessor’s value, then delete the successor/predecessor node, which will be a simpler case (leaf or one child).
Example: For deleting a node X:
1. If X is a leaf, remove it.
2. If X has one child, link X’s parent to X’s child.
3. If X has two children, find the in-order successor/predecessor, replace X’s value, and delete the successor/predecessor.
This process ensures the BST structure is preserved.