Think of values standing in line from smallest to largest: the successor of a value is the next value after it. In a tree, it is the node whose value immediately follows a given node in the tree’s ordering. section 11.14
For an element x in a collection without duplicates, the successor is the smallest element greater than x. The predecessor works in the opposite direction: it is the largest element smaller than x. section 11.14
How finding a successor changes with the data structure:
- In a sorted array or sorted doubly linked list, the successor is the adjacent element after x, when one exists. section 11.14
- In an unsorted array or linked structure, finding the successor can require scanning the entire container. section 11.14
- In a binary search tree, the operation follows the tree’s ordering but is not constant-time; successor and predecessor take O(h), where h is the tree height. section 11.14 section 11.20
Finding a predecessor reveals the pattern
For a node N, a predecessor may be the maximum value in N’s left subtree. Without a left subtree, it may be N’s parent when N is a right child; otherwise, climb upward until a node is a right child. Successor follows the corresponding ordering in the other direction. section 11.14
A singly linked list uses successor in a simpler structural sense: each node stores a link to the next node, its successor. Because nodes do not store predecessor links, deletion must retain the previous node so its link can bypass the removed node. section 6.4 section 6.9
Use the figure to visualize successor and predecessor relationships in a binary search tree. section 11.14
