Searching for values in a tree

There are three types of searches that are usually performed in trees:

• Searching for minimum values
• Searching for maximum values
• Searching for a specific value

Let’s take a look at each one in the following topics.

Searching for minimum and maximum values

Consider 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 leftmost node in the last level of the 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 value 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, as follows:

min() {
  return this.minNode(this.root); // {1}
}

The min...