There are three types of searches that are usually performed in trees:
Minimum values
Maximum values
Searching for a specific value
Let's take a look at each one.
Let's use the following tree for our examples:
Just looking at the preceding figure, could you easily find the minimum and maximum values of the tree?
If you take a look at the left-most node in the last level of tree, you will find the value 3, which is the lowest key from this tree. And if you take a look at the node that is furthest to the right (also in the last level of the tree), you will find the key 25, which is the highest key in this tree. This information helps us a lot when implementing methods that will find the minimum and maximum nodes of the tree.
First, let's take a look at the method that will find the minimum key of the tree:
this.min = function() {
return minNode(root); //{1}
};The min method will be the method exposed to the user. This method...