15.4. Predecessor Function

So, let us first look at successor, so recall that the successor of x in the list, supposed to be the next value, the next smallest value after x the list. So, if we print it out in sorted order, it will be the value that would appear to the right of x and the in order traversal of a tree prints out the values in sorted order.

The concept of a successor in a binary search tree refers to the next value in sorted order that follows a given node, denoted here as 'x'. When the tree is traversed using in-order traversal (visiting the left subtree, the node, and then the right subtree), the successor is the smallest value found in the right subtree of 'x'. If 'x' has no right subtree, the successor must be found by tracing back up the tree to find the first ancestor of 'x' that is a left child of its parent.

Imagine a library organized by the alphabetical order of book titles. If you are looking at a book titled 'Zebra' (representing 'x'), the successor would be the book that comes immediately after 'Zebra' in alphabetical order. If 'Zebra' has no books to the right on the shelf (no right subtree), you would need to ask the librarian (the ancestral nodes) to find out which book comes before 'Zebra'.

So, if you want to one that comes immediately after x, it will be the first value here. So, the smallest value in the right sub tree, in other words, the minimum of the right sub tree and we already know how to compute the minimum of a tree.

When a node 'x' has a right subtree, we can directly find its successor by looking for the minimum value within that right subtree. The minimum value in this context means the leftmost node of that subtree, as it is guaranteed to be the smallest element greater than 'x'.

Continuing with the library analogy, if 'Zebra' has a section dedicated to books starting with 'A' through 'M' (its right subtree), the successor would be 'Antelope', being the first book after 'Zebra' to the immediate right.

So, the first observation is that if a value has no right sub tree, then it must be the maximum of the sub tree to which it belongs.

If 'x' does not have a right subtree, we must determine its successor by tracing back up the tree. We follow the tree's upward path through right pointers until we find a node that is a left child of its parent. This parent node will be the successor of 'x' since it is the next greater element following 'x'.

Think of this as finding your way to the closest taller building when you’re standing next to a shorter one. If you're in a block of buildings where your building is the tallest but not a part of a taller section (no right subtree), you'd head back along the blocks until you find the first building that is taller than yours.

So, here is a simple pseudo code for this, so we want to find the successor of node t. Now, if this node has a right pointer, then we just return the minimum value of the right sub tree.

The process of finding a successor involves checking if the node 't' has a right child. If it does, it is straightforward, and we can immediately determine the successor as the smallest node in that right subtree. If not, we must traverse back to find the first parent node that indicates a point where we moved to a left child, thus identifying our successor node.

Imagine again that you’re looking for the next available parking space after you, represented by node 't'. If there’s a parking section directly after yours (right subtree), you take that space. However, if your section doesn’t have available spaces, you retrace your steps, looking for where you initially saw an open space (left child) helping find the next available spot.

So, the situation for the predecessor is symmetric, so if we have a left sub tree, then the predecessor is the maximum value in this.

In contrast to successsors, a predecessor of a node 'x' is the largest value that is smaller than 'x'. If 'x' has a left subtree, we can find the predecessor by determining the maximum value within that subtree, which will be the rightmost node of that subtree. If 'x' has no left subtree, we again look up the tree to find the node that represents the first right turn, which will be the predecessor.

Visualize a person trying to find the largest item smaller than the one they are holding—like comparing books at the store. If there’s a stack of books to the left (left subtree) that are smaller, the tallest one in that stack (the maximum) is just shortly less than what you're holding. Otherwise, if there’s no stack, you must retrace through the aisles (upward tree) until you reach the largest title that is still smaller than yours.

So, for example if you look at these values which have left sub trees, so for 5 we go down the left sub tree and we find the right most value which is 4.

To find predecessors, we first look for nodes with left sub trees. The maximum value from within that subtree can be determined by moving down to the leftmost node and then navigating to the rightmost node from there. If a node has no left subtree, trace up to the ancestor where you found a left-turn (left child), which indicates the predecessor. This process follows similar logic as the process for finding successors, just adjusted for smaller values.

Think of this situation like someone hunting for the largest book in their living room but only considering the smaller boxes (left sub tree). They check the tallest book sitting in a box or if there's no smaller box, they look through the room until they identify the adjacent shorter books on the nearby shelf.

--