Lab 11: Hint 2

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 nullptr:

      1. Return false.

   2. Otherwise:

      1. “Pass the buck” by returning whatever myLeft->contains(item) returns.

2. Otherwise, if item is greater than myItem:

   1. If myRight is nullptr:

      1. Return false.

   2. Otherwise:

      1. “Pass the buck” by returning whatever myRight->contains(item) returns.

3. Otherwise (item is equal to myItem):

   1. Return true.