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:
  2. Otherwise (there is at least one node):
  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:

Induction Step. Again, there are two cases:

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