Defining BST::contains()

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

   bool BST::contains(const Item& item) const {
   }

• If the BST is empty: return false.
• Otherwise: "pass the buck" by returning whatever myRoot->contains(item) returns.

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:

• If item is equal to myItem:
  • Return true.
• If item belongs in my left subtree and my left subtree is empty:
  • Return false.
• If item belongs in my right subtree and my right subtree is empty:
  • Return false.

Induction Step. There are two cases:

• If item belongs in my left subtree and my left subtree is not empty:
  • "Pass the buck" to the node in my left subtree and return whatever it returns.
• If item belongs in my right subtree and my right subtree is not empty:
  • "Pass the buck" to the node in my right subtree and return whatever it returns.

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 nullptr:
   • 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 nullptr:
      • Return false.
   2. Otherwise:
      • "Pass the buck" by returning whatever myRight->contains(item) returns.
3. Otherwise (item is equal to myItem):
   • Return true.