Predecessor Function

Today we'll learn how to find the minimum value in a binary search tree. Can anyone tell me how we might locate the minimum value?

Isn’t it the left-most node?

That's correct! The minimum value is the left-most node because all values to the left are smaller. We keep traversing left until we can't anymore.

What if we used a method to avoid recursion?

We can definitely use an iterative approach by starting at the root and continuously moving left until we reach a nil node. Great thinking! So if we start at a node with value 5 and go left, we would go to 3, then to 1, where we stop.

If I understand correctly, if we reach a node where left is nil, that's our minimum?

Exactly! To recap: finding the minimum involves a continuous left traversal until you can’t anymore. Now let’s summarize this: Minimum is found by always going left! Let's move on to maximum.

Now, what can you tell me about finding the maximum node in a BST?

Is it the right-most node?

Yes! Just like with the minimum, the maximum is found at the right-most end. All values to the right of a node are larger.

So we would follow the right links until we can’t go right anymore?

Great job! We keep moving to the right until reaching a nil node, and that last valid node we reached will be the maximum.

So if I take a node with value 5 and go to 7, then 9, I can't go right anymore, so 9 is maximum!

Exactly! Now let’s summarize: Maximum is found by always going right! Very good. Let's transition to the topic of predecessor and successor.

Now, who can tell me what the successor of a node is?

Isn't it the next larger value in order?

Yes! The successor of a node is the next value in in-order traversal. If the node has a right subtree, its successor is the minimum node of that subtree.

What about if it doesn’t have a right subtree?

Good question! In that case, we need to go up the parent nodes until we find the first left child. That parent becomes the successor.

So we could say that if there’s no right, we look up to find where we turned left?

Exactly! Great connection. Let's summarize: If it has a right subtree, it's the right subtree’s minimum; if not, we navigate upward to find where we turned left.

What can you tell me about the predecessor function?

Is it the largest value less than a given node?

Correct! For a node with a left subtree, the predecessor is the maximum of that subtree.

And if there’s no left subtree?

In that situation, we trace the parent links until we turn right. That node turns out to be the predecessor.

So for example, if from node 5 we go left to 4, 4 is predecessor?

Exactly right! And if there’s no left option, we navigate back up to find where we turned right. Let’s wrap this session up by reiterating the major points: Predecessor is found via the left subtree’s maximum or by ascending to where we turned right.