// fragment - insert an item to binary search tree - recursive version

 TreeNode<T> insertItem(TreeNode<T> n, T newItem)
  // returns a reference to the new root of the subtree rooted in n
  {
    TreeNode<T> newSubtree;
    if (n == null) {
      // position of insertion found; insert after leaf
      // create a new node
      n = new TreeNode<T>(newItem, null, null);
      return n;
    }  // end if
      
    // search for the insertion position
    if (newItem.getKey() < n.getItem().getKey()) {
      // search the left subtree
      newSubtree = insertItem(n.getLeft(), newItem);
      n.setLeft(newSubtree);
      return n;
    }
    else { // search the right subtree
      newSubtree = insertItem(n.getRight(), newItem);
      n.setRight(newSubtree);
      return n;
    }  // end if
  }  // end insertItem