BST Operations: Pseudocode (Part 2)

The getMin and getMax functions

Another property of a binary search tree is that we can find the minimum and maximum elements without sorting the data.

Look again at our binary search tree. If we look at the nodes, we see that:

• 1 is the minimum value and the leftmost node of the tree.
• 9 is the maximum value and the rightmost node of the tree.

Therefore, to find the minimum, we can go left as much as possible and stop before we reach NULL. To find the maximum, we can go right as much as possible and stop before we reach NULL.

Let’s write the pseudocode for the getMin function. ...