CS 112 Lab 9: BST::insert() Hint

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

   void BST::insert(const Item& it) {
   }

The BST::insert() method should distinguish between the two cases:

If the BST is empty:
- Create a new node containing it and store that node's address in myRoot.
Otherwise (there is at least one node):
- Try to "pass the buck" by sending Node::insert(it) to the node whose address is in myRoot.
- Catch any exception it throws; throw it on to the sender of the insert() message.
In either case (when no exception was thrown), increment myNumItems.

Since a Node is recursively defined, Node::insert(it) is a recursive method that should behave as follows:

If myLeft is NULL:
- Set myLeft to the address of a new node containing it.
Otherwise:
- "Pass the buck" by recursively calling myLeft->insert(it).

Otherwise, if it is greater than myItem:
1. If myRight is NULL:
  - Set myRight to the address of a new node containing it.
2. Otherwise:
  - "Pass the buck" by recursively calling myRight->insert(it).
Otherwise (it is equal to myItem):
- throw an Exception indicating that it is already in the BST.