#### 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:
• 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 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):
• Return true.