Lab 11: Hint

Declaring BST::insert()¶

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

void BST::insert(const Item& item) {

 }

Defining BST::insert()¶

The BST::insert(item) method needs to distinguish between the two cases (empty and non-empty):

1. If the BST is empty:

   • Create a new node containing item and store that node’s address in myRoot.

2. Otherwise (there is at least one node):

   • “Pass the buck” to the root node by invoking Node::insert(item) on the node whose address is in myRoot.

   • Any exception it throws will be sent back to the calling insert() message.

3. In either case (when no exception was thrown), increment myNumItems.

Designing Node::insert()¶

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

Basis. There are three trivial cases:

• If item belongs in my left subtree and my left subtree is empty:

  • Make my left subtree a new node containing item.

• If item belongs in my right subtree and my right subtree is empty:

  • Make my right subtree a new node containing item.

• If item does not belong in our left or right subtrees (i.e., its value is the same as myItem):

  • We will treat our BST like a mathematical set (which has no redundant elements) and throw an exception to alert the user that they have inserted the same Item more than once.

Induction Step. Again, 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 by asking it to insert item.

• If item belongs in my right subtree and my right subtree is not empty:

  • “Pass the buck” to the node in my right subtree by asking it to insert item.

Defining Node::insert()¶

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

1. If item is less than myItem:

   1. If myLeft is nullptr:

      1. Set myLeft to the address of a new node containing item.

   2. Otherwise:

      1. “Pass the buck” by recursively calling myLeft->insert(item).

2. Otherwise, if item is greater than myItem:

   1. If myRight is nullptr:

      1. Set myRight to the address of a new node containing item.

   2. Otherwise:

      1. “Pass the buck” by recursively calling myRight->insert(item).

3. Otherwise (item must be equal to myItem):

   1. throw an Exception indicating that item is already in the BST.