I'm studying algorithms on the very famous book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. and I'm looking at the algorithms for finding the maximum and minimum elements in a binary search tree . In the book obviously such a tree is described as follows:
"We can represent such a tree by a linked data structure in which each node is an object. In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate attribute contains the value NIL."
The pseudo code given in the book for finding the maximum is as follows:
TREE-MAXIMUM(x)
while x.right != NIL
x = x.rigth
return x
My question is: doesn't this code always return NIL? knowing the properties of the binary search tree: so when there is a right-hand subtree the maximum node is substantially the last node at the bottom right. If we follow the pseudo algorithm code above the while loop will terminate at the moment x == NIL and will always be equal to NILL in this algorithm. So it will always return NILL. Wouldn't this pseudocode be more correct? :
TREE-MAXIMUM(x)
while x.right != NIL
y=x
x = x.rigth
return y