// Fragment - deleteNode - iterative version

TreeNode<T> deleteNode(TreeNode<T> n) {
  // Returns a reference to a node which replaced n.
    // Algorithm note: There are four cases to consider:
    //   1. The n is a leaf.
    //   2. The n has no left child.
    //   3. The n has no right child.
    //   4. The n has two children.
    // Calls: findLeftmost and deleteLeftmost
  
    // test for a leaf
    if (n.getLeft() == null && n.getRight() == null)
      return null;
         
    // test for no left child
    if (n.getLeft() == null)
      return n.getRight();
         
    // test for no right child
    if (n.getRight() == null)
      return n.getLeft();
         
    // there are two children: retrieve and delete the inorder successor
    T replacementItem = findLeftMost(n.getRight()).getItem();
    n.setItem(replacementItem);
    n.setRight(deleteLeftMost(n.getRight()));
    return n;
  }  // end deleteNode

 TreeNode<T> findLeftmost(TreeNode<T> n)  {
    if (n.getLeft() == null) {
      return n;
    }
    else {
      return findLeftmost(n.getLeft());
    }  // end if
  }  // end findLeftmost
   
  TreeNode<T> deleteLeftmost(TreeNode<T> n)
  // Returns a new root.
  {
    if (n.getLeft() == null) {
      return n.getRight();
    }
    else {
      n.setLeft(deleteLeftmost(n.getLeft()));
      return n;
    }  // end if
  }  // end deleteLeftmost