Nullpointer exception and Stack overflow on recursive AVL tree balance method

Question

I have been trying for a long time to fix these problems with my tree program. I'm trying to build a refference based AVL tree that will keep itself balanced, The following methods are what are giving me the stack overflow and Nullpointer exception. I clearly need to work on my debugging skills but any advice that you could give me is really appreciated.

public AVLNode balance(AVLNode r){
System.out.println("start of balance");
if (r.getBalance()==r.MORE_LEFT){ /* dont need to check if r.hasLeft after this
  statement because if it passes has more left then it must have
  at least a left node */
  //if the left node has more attachments either left or right ways
    if(r.getLeft().getBalance()!=r.EVEN){
      System.out.println("r,MORE_LEFT && nextLeft is uneven");
      //calculateBalance(r);
      r.setLeft(balance(r.getLeft()));
    }else{
      System.out.println("doing the shift for "+(String)r.getElement());
      AVLNode shift=new AVLNode(r.getKey(), r.getElement(), null, r.getRight(), r.getBalance());
      r=balance(r.getLeft());
      insert(r, shift);
    }
//else if the Right side has more of the unbalance
}else if (r.getBalance()==r.MORE_RIGHT){
  if(r.getRight().getBalance()!=r.EVEN){
    System.out.println("r.MORE_RIGHT && nextRight is uneven");
    r.setRight(balance(r.getRight()));
  }
  else{
    System.out.println("doing the shift for "+(String)r.getElement());
    AVLNode shift=new AVLNode(r.getKey(), r.getElement(), r.getLeft(), null, r.getBalance());
    r=balance(r.getRight());
    insert(r,shift);
  }
}
if (r.hasLeft()) {
  System.out.println("botom left if run");
  r.setLeft(balance(r.getLeft()));
}
if (r.hasRight()) {
  System.out.println("bottom right if run");
  r.setRight(balance(r.getRight()));
}
return r;

}

 public void calculateBalance(AVLNode r){
    if (r!=null) {
      if (!r.hasRight() && !r.hasLeft())
        r.setBalance(r.EVEN);
      else {
        int rDeep=0;
        int lDeep=0;
        if (r.hasRight()) {
          rDeep=depth(r.getRight());
          calculateBalance(r.getRight());
        }
        if (r.hasLeft()) {
          lDeep=depth(r.getLeft());
          calculateBalance(r.getLeft());
        }
        if (lDeep>=2+rDeep){
          System.out.println("Node "+(String)r.getElement()+" has balance MORE_LEFT");
          r.setBalance(r.MORE_LEFT);
        }
        else if (rDeep>=2+lDeep){
          System.out.println("Node "+(String)r.getElement()+" has balance MORE_RIGHT");
          r.setBalance(r.MORE_RIGHT);
        }
        else{
          System.out.println("Node "+(String)r.getElement()+" has balance EVEN");
          r.setBalance(r.EVEN);
        }
      }
    }else System.out.println("null passed to calculateBalance You got splainin!!!");
  }
public int depth(AVLNode r){
if(r==null) return 0;
int max=Math.max(1+depth(r.getLeft()), 1+depth(r.getRight()));
System.out.println(""+max);
return max;
 //the number that is greater
//two options, go left or right count both and chose the greater one

} Here is the stack trace to show where I'm getting the error:

Level 1: VR 
Level 2: US WQ 
Level 3: GX 
Level 4: QE 
balanced 1 times.
start of balance
r,MORE_LEFT && nextLeft is uneven
start of balance
doing the shift for US
start of balance
bottom right if run
start of balance
bottom right if run
start of balance
bottom right if run
start of balance
Exception in thread "main" java.lang.NullPointerException
    at AVLDictionary.balance(AVLDictionary.java:64)
    at AVLDictionary.balance(AVLDictionary.java:93)
    at AVLDictionary.balance(AVLDictionary.java:93)
    at AVLDictionary.balance(AVLDictionary.java:67)
    at AVLDictionary.insert(AVLDictionary.java:42)
    at DictionaryAdvancedTest.main(DictionaryAdvancedTest.java:36)