Defining BST::contains()

The stub of BST::contains() should look like this:

   bool BST::contains(const Item& item) const {
   }
The BST::contains() method should distinguish between the two cases:

Designing Node::contains()

Since a Node is recursively defined, we might define Node::contains(item) recursively. One way to design a recursive algorithm for this method is as follows:

Basis. There are three trivial cases:

Induction Step. There are two cases:

Defining Node::contains()

These observations can be reorganized into the following algorithm for our Node::contains(item) method:

  1. If item is less than myItem:
    1. If myLeft is NULL:
      • Return false.
    2. Otherwise:
      • "Pass the buck" by returning whatever myLeft->contains(item) returns.
  2. Otherwise, if item is greater than myItem:
    1. If myRight is NULL:
      • Return false.
    2. Otherwise:
      • "Pass the buck" by returning whatever myRight->contains(item) returns.
  3. Otherwise (item is equal to myItem):