Trying to balance an AVL tree when adding (inserting) : Java

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:

package proj;

import java.util.LinkedList;
import java.util.Queue;

public class AVLTree<T extends Comparable<T>> {

    private Queue<Node<T>> tree;
    private Node<T> root;
    private int size;

    public AVLTree(){
        tree = new LinkedList<Node<T>>();
        root = null;
        size = 0;
    }

    public void add(T value){
        Node<T> n = new Node<T>(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<T> subtree, T value){
        Node<T> n = new Node<T>(value);

        if(subtree == null){
            subtree = n开发者_开发百科;

            tree.add(n);
            size++;
            if(size()>2){
                balance(n.getParent());
            }
        }
        else{
            int difference = subtree.getValue().compareTo(n.getValue());
            if(difference<0){
                if(subtree.getRightChild()==null){
                    subtree.setRightChild(n);
                    n.setParent(subtree);

                    tree.add(n);
                    size++;

                    if(size()>2){
                        balance(n.getParent());
                    }
                }
                else{
                    add(subtree.getRightChild(), value);
                }
            }
            else if(difference>0){
                if(subtree.getLeftChild()==null){
                    subtree.setLeftChild(n);
                    n.setParent(subtree);

                    tree.add(n);
                    size++;
                    if(size()>2){
                        balance(n.getParent());
                    }
                }
                else{
                    add(subtree.getLeftChild(), value);
                }
            }
            else if(difference==0){
                return;
            }
        }
    }

    //balances the tree
    public void balance(Node<T> n){
        if(balanceFactor(n) == -2){
            if(balanceFactor(n.getRightChild())<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())>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<T> subtree){
        Node<T> 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<T> subtree){
        Node<T> temp = subtree.getLeftChild();
        subtree.setLeftChild(temp.getRightChild());
        temp.setRightChild(subtree);
        subtree = temp;
    }

    //returns the tree in its current state
    public Queue<Node<T>> getTree(){
        return tree;
    }

    //returns the root of the tree
    public Node<T> getRoot(){
        return root;
    }

    //returns the size of the tree
    public int size(){
        return size;
    }

    //returns the head of the queue
    public Node<T> peek(){
        Node<T> 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<T> 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<T> subtree){
            return height(subtree.getLeftChild()) - height(subtree.getRightChild());
    }

    public static void main(String[] args){
        AVLTree<Integer> avl = new AVLTree<Integer>();
        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<Integer> n : avl.tree){
            System.out.println(n.getValue());
        }
    }
}

Am I doing the methods I mentioned incorrectly, or am I incorrectly adding to the tree before I even get to the balancing?

I'll edit this once in a while until you get the answer:

1) When AvlTree.add() is called with parameters (null, whatever) the subtree parameter is replaced with a brand new node. Further on if the size of the tree is greater than 2 then balance(n.getParent()) is called. I would guess that n.getParent() would always return null in this case. When balance() has been called, the first thing done is balanceFactor(null) that will cause a NPE on the line that causes NPE.