/** * Internal method to remove from a subtree. * @param x the item to remove. * @param t the node that roots the tree. * @return the new root. * @throws ItemNotFoundException if x is not found. */ protected BinaryNode remove( AnyType x, BinaryNode t ) { if( t == null ) throw new ItemNotFoundException( x.toString( ) ); if( x.compareTo( t.element ) < 0 ) t.left = remove( x, t.left ); else if( x.compareTo( t.element ) > 0 ) t.right = remove( x, t.right ); else if( t.left != null && t.right != null ) // Two children { t.element = findMin( t.right ).element; t.right = removeMin( t.right ); } else t = ( t.left != null ) ? t.left : t.right; return t; }