title: Trying to balance an AVL tree when adding (inserting) : Java
body: <p>I'm trying to balance my AVL tree after I add a new item to the tree, but I keep getting NPEs. I believe I've narrowed it down to something to do with my balance() method, or possibly more specifically, my rotateLeft() and rotateRight() methods. Here's my AVLTree class:</p>
  
  <pre><code>package proj;
  
  import java.util.LinkedList;
  import java.util.Queue;
  
  public class AVLTree&lt;T extends Comparable&lt;T&gt;&gt; {
  
      private Queue&lt;Node&lt;T&gt;&gt; tree;
      private Node&lt;T&gt; root;
      private int size;
  
      public AVLTree(){
          tree = new LinkedList&lt;Node&lt;T&gt;&gt;();
          root = null;
          size = 0;
      }
  
      public void add(T value){
          Node&lt;T&gt; n = new Node&lt;T&gt;(value);
  
          if(root == null){
              root = n;
              tree.add(n);
              size++;
          }
          else{
              add(root, value);
          }
      }
  
      //adds a new node to the tree then re-balances if necessary
      public void add(Node&lt;T&gt; subtree, T value){
          Node&lt;T&gt; n = new Node&lt;T&gt;(value);
  
          if(subtree == null){
              subtree = n;
  
              tree.add(n);
              size++;
              if(size()&gt;2){
                  balance(n.getParent());
              }
          }
          else{
              int difference = subtree.getValue().compareTo(n.getValue());
              if(difference&lt;0){
                  if(subtree.getRightChild()==null){
                      subtree.setRightChild(n);
                      n.setParent(subtree);
  
                      tree.add(n);
                      size++;
  
                      if(size()&gt;2){
                          balance(n.getParent());
                      }
                  }
                  else{
                      add(subtree.getRightChild(), value);
                  }
              }
              else if(difference&gt;0){
                  if(subtree.getLeftChild()==null){
                      subtree.setLeftChild(n);
                      n.setParent(subtree);
  
                      tree.add(n);
                      size++;
                      if(size()&gt;2){
                          balance(n.getParent());
                      }
                  }
                  else{
                      add(subtree.getLeftChild(), value);
                  }
              }
              else if(difference==0){
                  return;
              }
          }
      }
  
      //balances the tree
      public void balance(Node&lt;T&gt; n){
          if(balanceFactor(n) == -2){
              if(balanceFactor(n.getRightChild())&lt;0){
                  rotateLeft(n);
                  if(balanceFactor(n.getRightChild())==-1){
                      rotateLeft(n);
                      rotateLeft(n.getRightChild());
                  }
                  else if(balanceFactor(n.getRightChild())==1){
                      rotateRight(n.getRightChild());
                      rotateLeft(n);
                  }
              }
          }
          else if(balanceFactor(n) == 2){
              if(balanceFactor(n.getLeftChild())&gt;0){
                  rotateRight(n);
                  if(balanceFactor(n.getLeftChild())==1){
                      rotateRight(n);
                      rotateRight(n.getLeftChild());
                  }
                  else if(balanceFactor(n.getLeftChild())==-1){
                      rotateLeft(n.getLeftChild());
                      rotateRight(n);
                  }
              }
          }
          if(n.getParent() != null){
              balance(n.getParent());
          }
      }
  
      //performs a left rotation on the passed
      //subtree root
      public void rotateLeft(Node&lt;T&gt; subtree){
          Node&lt;T&gt; temp = subtree.getRightChild();
          subtree.setRightChild(temp.getLeftChild());
          temp.setLeftChild(subtree);
          subtree = temp;
      }
  
      //performs a right rotation on the passed
      //subtree root 
      public void rotateRight(Node&lt;T&gt; subtree){
          Node&lt;T&gt; temp = subtree.getLeftChild();
          subtree.setLeftChild(temp.getRightChild());
          temp.setRightChild(subtree);
          subtree = temp;
      }
  
      //returns the tree in its current state
      public Queue&lt;Node&lt;T&gt;&gt; getTree(){
          return tree;
      }
  
      //returns the root of the tree
      public Node&lt;T&gt; getRoot(){
          return root;
      }
  
      //returns the size of the tree
      public int size(){
          return size;
      }
  
      //returns the head of the queue
      public Node&lt;T&gt; peek(){
          Node&lt;T&gt; current = root;
          while(current.getLeftChild() != null){
              current = current.getLeftChild();
          }
          return current;
      }
  
      //returns the height of the tree; returns -1 if the tree is empty
      public int height(Node&lt;T&gt; n){
          if(n == null){
              return -1;
          }
          return Math.max(height(n.getLeftChild()), height(n.getRightChild()))+ 1;
      }
  
      //returns the balance factor of the passed subtree
      public int balanceFactor(Node&lt;T&gt; subtree){
              return height(subtree.getLeftChild()) - height(subtree.getRightChild());
      }
  
      public static void main(String[] args){
          AVLTree&lt;Integer&gt; avl = new AVLTree&lt;Integer&gt;();
          avl.add(1);
          avl.add(2);
          avl.add(3);
          avl.add(4);
          avl.add(5);
  
          System.out.println("Root: " + avl.root.getValue());
          System.out.println("Root's left: " + avl.root.getRightChild().getValue());
  
          System.out.println("Root's balance factor: " + avl.balanceFactor(avl.getRoot()));
          System.out.println("Tree Size: " + avl.size());
          for(Node&lt;Integer&gt; n : avl.tree){
              System.out.println(n.getValue());
          }
      }
  }
  </code></pre>
  
  <p>Am I doing the methods I mentioned incorrectly, or am I incorrectly adding to the tree before I even get to the balancing?</p>