15.3. Successor 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. So, it is effectively what in order would print immediately after x. So, we know that the way that in order works, it prints the left sub tree then it prints x, then it prints right sub tree.

The successor function identifies the next value that follows a specified value (x) in a sorted list derived from a binary search tree (BST). When we perform an in-order traversal of the tree, we access nodes in non-decreasing order. Therefore, the successor of any node x is simply the smallest value in the right subtree of x, as this value is the next largest value after x in sorted order.

Imagine a bookshelf organized by author names in alphabetical order. If you are looking for the next author right after 'John', you would look at the books that come after John's section on the shelf. The first book you find there, say from 'Johnson', represents the next author or 'successor' following 'John'.

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, but they could be a possibility that we want to successor of a value with does not have a right sub tree, then what we do.

When the node x has a right subtree, finding the successor is straightforward. We simply navigate to the right child of x and then continue moving left until we reach the leftmost node of that right subtree. This leftmost node is the smallest value in the subtree, thereby serving as the successor of x.

Imagine you are in a library and want to go to the next aisle after 'History'. You walk into the 'Science' aisle and then head towards the leftmost book on the shelf there. The first book you find will be the 'next' book you need, just like how we find the successor by going to the leftmost node in the right subtree.

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. So, in this case we look at the value x, it has no right sub trees, so it is the maximum of some sub tree.

If a node x does not have a right subtree, we still need to find its successor. In this case, the successor of x will be an ancestor node. To identify it, we backtrack the path from node x to its ancestors. We look for the first ancestor node where we took a left turn (indicating we haven't gone to the end of that subtree yet). This ancestor will be the successor of x.

Consider playing a treasure-hunting game where a player can only move forward or backward. If you always go forward till you can't anymore (no right turn), you can backtrack until you find the last point you can still make a valid move (left turn). That point signifies the next immediate spot to explore, much like finding the successor.

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, on the other hand if it does not have a right, then we need to go up and find the first place where the part turns right.

The pseudo code for the successor function operates by first checking if the node t has a right child. If it does, we use the function for finding the minimum value in that right subtree. If t does not have a right child, we backtrack using parent pointers until we find a node that is a left child to its parent, indicating that this parent is the successor node.

This is like navigating through a maze. If you hit a dead end, you retrace your steps back to the last junction where you could have taken a different path (turning right) before you reached that dead end. That node would be your 'successor' route.

--