title: Underflow Exception error in java
body: <p>I am creating a AvlTree program. I am trying to implement a UnderflowException class within my code but it seems not to work. Shouldn't be possible? or I'm doing something wrong. </p>
  
  <p>My code:</p>
  
  <pre><code>public class AvlTree&lt;AnyType extends Comparable&lt;? super AnyType&gt;&gt;
  {
      /**
       * Construct the tree.
       */
      public AvlTree( )
      {
          root = null;
      }
  
      /**
       * Insert into the tree; duplicates are ignored.
       * @param x the item to insert.
       */
      public void insert( AnyType x )
      {
          root = insert( x, root );
      }
  
      /**
       * Remove from the tree. Nothing is done if x is not found.
       * @param x the item to remove.
       */
      public void remove( AnyType x )
      {
          root = remove( x, root );
      }
  
  
      /**
       * Internal method to remove from a subtree.
       * @param x the item to remove.
       * @param t the node that roots the subtree.
       * @return the new root of the subtree.
       */
      private AvlNode&lt;AnyType&gt; remove( AnyType x, AvlNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return t;   // Item not found; do nothing
  
          int compareResult = x.compareTo( t.element );
  
          if( compareResult &lt; 0 )
              t.left = remove( x, t.left );
          else if( compareResult &gt; 0 )
              t.right = remove( x, t.right );
          else if( t.left != null &amp;&amp; t.right != null ) // Two children
          {
              t.element = findMin( t.right ).element;
              t.right = remove( t.element, t.right );
          }
          else
              t = ( t.left != null ) ? t.left : t.right;
          return balance( t );
      }
  
      /**
       * Find the smallest item in the tree.
       * @return smallest item or null if empty.
       */
      public AnyType findMin( ) throws UnderflowException
      {
          if( isEmpty( ) )
              throw new UnderflowException("Error" );
          return findMin( root ).element;
      }
  
      /**
       * Find the largest item in the tree.
       * @return the largest item of null if empty.
       */
      public AnyType findMax( ) throws UnderflowException
      {
          if( isEmpty( ) )
              throw new UnderflowException("Error" );
          return findMax( root ).element;
      }
  
      /**
       * Find an item in the tree.
       * @param x the item to search for.
       * @return true if x is found.
       */
      public boolean contains( AnyType x )
      {
          return contains( x, root );
      }
  
      /**
       * Make the tree logically empty.
       */
      public void makeEmpty( )
      {
          root = null;
      }
  
      /**
       * Test if the tree is logically empty.
       * @return true if empty, false otherwise.
       */
      public boolean isEmpty( )
      {
          return root == null;
      }
  
      /**
       * Print the tree contents in sorted order.
       */
      public void printTree( )
      {
          if( isEmpty( ) )
              System.out.println( "Empty tree" );
          else
              printTree( root );
      }
  
      private static final int ALLOWED_IMBALANCE = 1;
  
      // Assume t is either balanced or within one of being balanced
      private AvlNode&lt;AnyType&gt; balance( AvlNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return t;
  
          if( height( t.left ) - height( t.right ) &gt; ALLOWED_IMBALANCE )
              if( height( t.left.left ) &gt;= height( t.left.right ) )
                  t = rotateWithLeftChild( t );
              else
                  t = doubleWithLeftChild( t );
          else
          if( height( t.right ) - height( t.left ) &gt; ALLOWED_IMBALANCE )
              if( height( t.right.right ) &gt;= height( t.right.left ) )
                  t = rotateWithRightChild( t );
              else
                  t = doubleWithRightChild( t );
  
          t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
          return t;
      }
  
      public void checkBalance( )
      {
          checkBalance( root );
      }
  
      private int checkBalance( AvlNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return -1;
  
          if( t != null )
          {
              int hl = checkBalance( t.left );
              int hr = checkBalance( t.right );
              if( Math.abs( height( t.left ) - height( t.right ) ) &gt; 1 ||
                      height( t.left ) != hl || height( t.right ) != hr )
                  System.out.println( "OOPS!!" );
          }
  
          return height( t );
      }
  
  
      /**
       * Internal method to insert into a subtree.
       * @param x the item to insert.
       * @param t the node that roots the subtree.
       * @return the new root of the subtree.
       */
      private AvlNode&lt;AnyType&gt; insert( AnyType x, AvlNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return new AvlNode&lt;AnyType&gt;( x, null, null );
  
          int compareResult = x.compareTo( t.element );
  
          if( compareResult &lt; 0 )
              t.left = insert( x, t.left );
          else if( compareResult &gt; 0 )
              t.right = insert( x, t.right );
          else
              ;  // Duplicate; do nothing
          return balance( t );
      }
  
      /**
       * Internal method to find the smallest item in a subtree.
       * @param t the node that roots the tree.
       * @return node containing the smallest item.
       */
      private AvlNode&lt;AnyType&gt; findMin( AvlNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return t;
  
          while( t.left != null )
              t = t.left;
          return t;
      }
  
      /**
       * Internal method to find the largest item in a subtree.
       * @param t the node that roots the tree.
       * @return node containing the largest item.
       */
      private AvlNode&lt;AnyType&gt; findMax( AvlNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return t;
  
          while( t.right != null )
              t = t.right;
          return t;
      }
  
      /**
       * Internal method to find an item in a subtree.
       * @param x is item to search for.
       * @param t the node that roots the tree.
       * @return true if x is found in subtree.
       */
      private boolean contains( AnyType x, AvlNode&lt;AnyType&gt; t )
      {
          while( t != null )
          {
              int compareResult = x.compareTo( t.element );
  
              if( compareResult &lt; 0 )
                  t = t.left;
              else if( compareResult &gt; 0 )
                  t = t.right;
              else
                  return true;    // Match
          }
  
          return false;   // No match
      }
  
      /**
       * Internal method to print a subtree in sorted order.
       * @param t the node that roots the tree.
       */
      private void printTree( AvlNode&lt;AnyType&gt; t )
      {
          if( t != null )
          {
              printTree( t.left );
              System.out.println( t.element );
              printTree( t.right );
          }
      }
  
      /**
       * Return the height of node t, or -1, if null.
       */
      private int height( AvlNode&lt;AnyType&gt; t )
      {
          return t == null ? -1 : t.height;
      }
  
      /**
       * Rotate binary tree node with left child.
       * For AVL trees, this is a single rotation for case 1.
       * Update heights, then return new root.
       */
      private AvlNode&lt;AnyType&gt; rotateWithLeftChild( AvlNode&lt;AnyType&gt; k2 )
      {
          AvlNode&lt;AnyType&gt; k1 = k2.left;
          k2.left = k1.right;
          k1.right = k2;
          k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
          k1.height = Math.max( height( k1.left ), k2.height ) + 1;
          return k1;
      }
  
      /**
       * Rotate binary tree node with right child.
       * For AVL trees, this is a single rotation for case 4.
       * Update heights, then return new root.
       */
      private AvlNode&lt;AnyType&gt; rotateWithRightChild( AvlNode&lt;AnyType&gt; k1 )
      {
          AvlNode&lt;AnyType&gt; k2 = k1.right;
          k1.right = k2.left;
          k2.left = k1;
          k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
          k2.height = Math.max( height( k2.right ), k1.height ) + 1;
          return k2;
      }
  
      /**
       * Double rotate binary tree node: first left child
       * with its right child; then node k3 with new left child.
       * For AVL trees, this is a double rotation for case 2.
       * Update heights, then return new root.
       */
      private AvlNode&lt;AnyType&gt; doubleWithLeftChild( AvlNode&lt;AnyType&gt; k3 )
      {
          k3.left = rotateWithRightChild( k3.left );
          return rotateWithLeftChild( k3 );
      }
  
      /**
       * Double rotate binary tree node: first right child
       * with its left child; then node k1 with new right child.
       * For AVL trees, this is a double rotation for case 3.
       * Update heights, then return new root.
       */
      private AvlNode&lt;AnyType&gt; doubleWithRightChild( AvlNode&lt;AnyType&gt; k1 )
      {
          k1.right = rotateWithLeftChild( k1.right );
          return rotateWithRightChild( k1 );
      }
  
      private static class AvlNode&lt;AnyType&gt;
      {
              // Constructors
          AvlNode( AnyType theElement )
          {
              this( theElement, null, null );
          }
  
          AvlNode( AnyType theElement, AvlNode&lt;AnyType&gt; lt, AvlNode&lt;AnyType&gt; rt )
          {
              element  = theElement;
              left     = lt;
              right    = rt;
              height   = 0;
          }
  
          AnyType           element;      // The data in the node
          AvlNode&lt;AnyType&gt;  left;         // Left child
          AvlNode&lt;AnyType&gt;  right;        // Right child
          int               height;       // Height
      }
  
        /** The tree root. */
      private AvlNode&lt;AnyType&gt; root;
  
  
          // Test program
      public static void main( String [ ] args )
      {
          AvlTree&lt;Integer&gt; t = new AvlTree&lt;Integer&gt;( );
          final int SMALL = 40;
          final int NUMS = 1000000;  // must be even
          final int GAP  =   37;
  
          System.out.println( "Checking... (no more output means success)" );
  
          for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
          {
          //    System.out.println( "INSERT: " + i );
              t.insert( i );
              if( NUMS &lt; SMALL )
                  t.checkBalance( );
          }
  
          for( int i = 1; i &lt; NUMS; i+= 2 )
          {
           //   System.out.println( "REMOVE: " + i );
              t.remove( i );
              if( NUMS &lt; SMALL )
                  t.checkBalance( );
          }
          if( NUMS &lt; SMALL )
              t.printTree( );
          if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
              System.out.println( "FindMin or FindMax error!" );
  
          for( int i = 2; i &lt; NUMS; i+=2 )
               if( !t.contains( i ) )
                   System.out.println( "Find error1!" );
  
          for( int i = 1; i &lt; NUMS; i+=2 )
          {
              if( t.contains( i ) )
                  System.out.println( "Find error2!" );
          }
      }
  
      /**
       *
       */
  
  public class UnderflowException extends RuntimeException {
      /**
       * Construct this exception object.
       * @param message the error message.
       */
      public UnderflowException( String message ) {
          super( message );
      }
  }
  }
  </code></pre>
  
  <p>So, the UnderflowExecption class will display a message "Error". I still get the result without any logic error but my compiler (Netbeans) keeps marking these part wrong.  Is my implementation wrong or is just my compiler? </p>