Imagine lining up a collection of distinct values from smallest to largest. The predecessor of a value is the one immediately before it. In a binary search tree (BST), that value may not be stored in an adjacent node, so finding it means following the tree’s links. section 11.14
To find a node’s predecessor in the whole BST:
- If the node has a left subtree, find the maximum value in that subtree. section 11.14
- Otherwise, if the node is a right child, its parent is the predecessor. section 11.14
- Otherwise, climb toward the root until you reach a node that is a right child. Its parent is the predecessor. If you reach the root without finding one, there is no predecessor: the starting node is the tree’s minimum. section 11.14
Replacing a node during deletion
Suppose the node containing 4 has two children, and the maximum value in its left subtree is 3. Replace 4 with its predecessor, 3, then delete the original node containing 3. That node cannot have a right subtree—otherwise 3 would not have been the left subtree’s maximum—so its removal is a simpler deletion case. section 11.11
A sorted array or sorted doubly linked list puts a present predecessor immediately before its value. A BST instead takes O(h) time to find one, where h is the tree’s height; in a balanced BST, that is O(log(n)). The parent-climbing description assumes access to parent links. Without them, implementation requires backtracking, which is left for further study. section 11.14 section 11.20
