In the delete operation of a BST, we need the inorder successor (or…

Concept

In deletion from a BST, when the node to be removed has two non-empty children, its value is replaced by its inorder successor -- the node with the smallest key larger than it. This successor is found by moving once into the right subtree and then repeatedly following left-child pointers until none remain, i.e., the leftmost node of the right subtree. Because inorder traversal visits keys in increasing order within a subtree, the leftmost node of any subtree is guaranteed to have no left child -- if it did, that left child would represent an even smaller key, contradicting the node being leftmost.

Application

The three cases for deleting a node X in a BST are:

1. X is a leaf: detach X directly from its parent.

2. X has exactly one non-empty child: splice that child's subtree into X's place.

3. X has two non-empty children: locate the inorder successor Y as the leftmost node in X's right subtree, copy Y's value into X, then delete Y (which now falls under case 1 or case 2 since Y has no left child).

Because Y is reached by always moving left inside X's right subtree, Y's left child is guaranteed to be empty. Y may or may not have a right child, so Y is either a leaf or a node with only a right child -- never the reverse, and never a node lying above X.

Cross-check

• The claim that the successor is always a leaf is too strong: only the left pointer is guaranteed empty, so the successor can still carry a right child.

• The claim that the successor may be an ancestor is impossible here: an ancestor of X lies on the path from the root to X, while this successor lies strictly inside X's right subtree -- the two regions cannot overlap.

• The claim that it is a leaf or has an empty right child has the sides reversed: repeatedly moving left inside the right subtree empties the left pointer, not the right one.