Data Structures, Algorithms, & Applications in Java
Chapter 15, Exercise 15

The max element is found by starting at the root and making as many right child moves as possible. The node at which this sequence of moves terminates has an empty right subtree and so can be deleted by changing the right child pointer of the parent node to point to the left child of the node being deleted. The code is given below. Its complexity is O(h) because we spend O(1) time at each level of the tree. 
public class BinarySearchTreeWithRemoveMax extends BinarySearchTree
{
   /** @return element with maximum key and remove it
     * @return null if tree is empty */
   public Object removeMax()
   {
      if (root == null)
         // tree is empty
         return null;

      // p will eventually point to node with maximum key
      BinaryTreeNode p = root,    // search pointer
                     pp = null;   // parent of p

      // follow right child pointers to element with maxkey
      while (p.rightChild != null)
      {// move to right child of p
         pp = p;
         p = p.rightChild;
      }

      // save element to be removed
      Object theElement = ((Data) p.element).element; 
   
      // remove node p from the tree, p has at most one child
      if (p == root)
         root = p.leftChild;
      else
         pp.rightChild = p.leftChild;
   
      return theElement;
   }
}