The Algorithm Design Manual Second Edition

Finding Minimum and Maximum Elements in a Tree

Implementing the find-minimum operation requires knowing where the minimum

element is in the tree. By definition, the smallest key must reside in the left subtree

of the root, since all keys in the left subtree have values less than that of the root.

Therefore, as shown in Figure

3.3

, the minimum element must be the leftmost

descendent of the root. Similarly, the maximum element must be the rightmost

descendent of the root.

tree *find_minimum(tree *t)

{

tree *min;

/* pointer to minimum */

if (t == NULL) return(NULL);

min = t;

while (min->left != NULL)

min = min->left;

return(min);

}