How to Implement Binary Search Tree Insertion and Deletion

In a Binary Search Tree, every node follows one rule: all values in its left subtree are smaller than the node and all values in its right subtree are greater. This property must be maintained after every insertion and deletion.

To insert a value, start at the root. If the value is smaller than the current node, move to the left child. If it is greater, move to the right child. Keep moving until you reach a NULL position. That NULL position is exactly where the new node belongs.

The base case of the recursive insertion function is when the current node is NULL. At that point, create a new node with the given value and return it. The parent's left or right pointer will automatically be set to this new node as the recursion unwinds.

To delete a value, first search for it using the same left-right comparison logic as insertion. If the value is smaller than the current node, recurse left. If it is greater, recurse right. If the current node is NULL, the value does not exist in the tree.

If the node to delete has no left child, return its right child to replace it. If it has no right child, return its left child to replace it. These two cases are straightforward because there is only one subtree to preserve.

This is the most complex case. Find the inorder successor, which is the smallest node in the right subtree. Copy the inorder successor's value into the current node. Then recursively delete the inorder successor from the right subtree, since it now exists in two places.

The inorder successor is the next largest value after the deleted node. Replacing the deleted node with it preserves the BST property because it is greater than everything in the left subtree and smaller than everything else in the right subtree.