#### 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):
• Try to "pass the buck" by sending Node::insert(item) to the node whose address is in myRoot.
• Catch any exception it throws; throw it on to the sender of the 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 NULL:
• Set myLeft to the address of a new node containing item.
2. Otherwise:
• "Pass the buck" by recursively calling myLeft->insert(item).
2. Otherwise, if item is greater than myItem:
1. If myRight is NULL:
• Set myRight to the address of a new node containing item.
2. Otherwise:
• "Pass the buck" by recursively calling myRight->insert(item).
3. Otherwise (item is equal to myItem):
• throw an Exception indicating that item is already in the BST.