Deleting a Node in BST

The Responsibility

A Binary Search Tree is not merely a collection of nodes. It is a disciplined structure governed by a simple invariant: for every node, values in the left subtree are smaller, and values in the right subtree are larger.

When deleting a node, we are not just removing memory. We are preserving order. The structure must continue to behave as a BST after the operation.

The Three Situations

Deleting a node in a BST is not complicated. But it is precise. There are exactly three structural possibilities.

1. Leaf Node (No Children)

This is the simplest case. The node has no children. Removing it does not disturb the structure. We simply detach it from its parent. The tree remains valid.

2. Node with One Child

Here the node has either a left child or a right child. Deleting it means connecting its parent directly to its only child. The child takes its place. The global structure remains correct.

3. Node with Two Children

This is the only case that demands deeper thinking. If we simply remove the node, we break ordering. So instead, we replace its value with a carefully chosen substitute, either:

• The maximum value from its left subtree (inorder predecessor), or
• The minimum value from its right subtree (inorder successor).

Why these? Because they are the closest values that preserve ordering. The inorder successor, for example, is the smallest value greater than the current node. By definition, it has no left child.

After copying the replacement value, we then delete that successor or predecessor node — which now falls into case 1 or case 2. Deletion becomes simpler.

Final Reflection

Most of the time, deletion is simple. Only when a node holds two subtrees do we need strategy.

By selecting a successor or predecessor as a replacement, the complexity reduces itself into one of the easier cases of deletion. The tree ensures that the structure remains consistent, and the search property continues to hold throughout the tree.