0
$\begingroup$

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
$\endgroup$

1 Answer 1

2
$\begingroup$

No. Try an example. The loop terminates when x.right == NIL. This is not the same as x == NIL.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.