in-order successor

The node with the next larger key in a binary search tree, which is the smallest key in the node's right subtree.

In more detail

Deleting a node with two children copies its in-order successor's key into it and then deletes the successor, which has at most one child. That reduces the hard case to one of the two easy ones: removing a leaf, or splicing out a node with one child.

Related terms

Taught in

References