// Fragment - deleteItem - recursive version

TreeNode<T> deleteItem(TreeNode<T> n, long searchKey) {
  // Returns a reference to the new root.
  // Calls: deleteNode.
    TreeNode<T> newSubtree;
    if (n == null) {
    throw new TreeException("TreeException: Item not found");
    }
    else {
      if (searchKey==n.getItem().getKey()) {
        // item is in the root of some subtree
        n = deleteNode(n);  // delete the node n
      }
      // else search for the item
      else if (searchKey<n.getItem().getKey()) {
        // search the left subtree
        newSubtree = deleteItem(n.getLeft(), searchKey);
        n.setLeft(newSubtree);
      }
      else { // search the right subtree
        newSubtree = deleteItem(n.getRight(), searchKey);
        n.setRight(newSubtree);
      }  // end if
    }  // end if
    return n;
  }  // end deleteItem