java - AVL Trees: How to properly rebalance? -

i'm writing avl tree class , professor has included tests our code. have passed tests except three, , 3 tests i'm failing seem indicate when elements added or removed tree, tree doesn't balance when necessary. i've been trying debug it, can't seem find error. please point out i'm missing?

edit: failed tests: removeroot - removes root of avl tree , replaces successor. addmanysingle - adds several elements , forces single rotation. addmanydouble - adds several elements , forces double rotation.

private int count, height; private avlnode < e > root;  public avltree() {     root = null;     count = 0;     height = 0; }  //the private inner node class private class avlnode < e > {      private int height, bf;     private e data;     private avlnode < e > left, right;      public avlnode() {         data = null;         left = right = null;         bf = 0;         height = 0;     }      public avlnode(e data) {         this.data = data;         left = right = null;         bf = 0;         height = 0;     }      public e getdata() {         return data;     }      public void setdata(e data) {         this.data = data;     }      public avlnode < e > getleft() {         return left;     }      public void setleft(avlnode < e > left) {         this.left = left;     }      public avlnode < e > getright() {         return right;     }      public void setright(avlnode < e > right) {         this.right = right;     }      public int getbf() {         return bf;     }      public void setbf() {         if (right == null && left == null) {             bf = 0;         } else if (right == null) {             bf = this.getleft().getheight();         } else if (left == null) {             bf = 0 - this.getright().getheight();         } else {             this.bf = this.getleft().getheight() - this.getright().getheight();         }     }      public void setbf(int thebalancefactor) {         bf = thebalancefactor;     }      /**      * getheight method computes height of avl tree.      * @return height of avl tree.      */     public int getheight() {         return == null ? -1 : this.height;     }      public void setheight() {         int leftheight = (left == null) ? -1 : left.getheight();         int rightheight = (right == null) ? -1 : right.getheight();         height = 1 + math.max(leftheight, rightheight);     }      public void setheight(int theheight) {         height = theheight;     } }  //the private inner iterator class private class avliterator implements iterator < e > {      private avlnode < e > nextnode;     private stack < avlnode < e >> stack;       public avliterator() {         nextnode = root;         stack = new stack < avlnode < e >> ();         while (root != null) {             stack.push(root);             root = root.getleft();         }     }      //returns true if iteration has more datas.     @override     public boolean hasnext() {         return !stack.isempty();     }      //returns next data in iteration.     @override     public e next() {         if (!hasnext()) {             throw new nosuchelementexception("no next element.");         }         avlnode < e > node = stack.pop();         e result = node.data;         if (node.right != null) {             node = node.right;             while (node != null) {                 stack.push(node);                 node = node.left;             }         }         return result;     }      //removes last data in iteration.     @override     public void remove() {         throw new unsupportedoperationexception("invalid operation support list.");     } }  /**  * rotate binary tree node has right child.  * update heights, return new root.  * n1 imbalanced node  */ private avlnode < e > rotatewithrightchild(avlnode < e > n1) {     avlnode < e > n2 = n1.right;     n1.right = n2.left;     n2.left = n1;     return n2; }  /**  * rotate binary tree node has left child.  * update heights, return new root.  */ private avlnode < e > rotatewithleftchild(avlnode < e > n2) {     avlnode < e > n1 = n2.left;     n2.left = n1.right;     n1.right = n2;     return n1; }  /**  * double rotate binary tree node: first left child  * right child; node n3 new left child.  * update heights, return new root.  */ private avlnode < e > doublewithleftchild(avlnode < e > n3) {     n3.left = rotatewithrightchild(n3.left);     return rotatewithleftchild(n3); }  /**  * double rotate binary tree node: first right child  * left child; node n1 new right child.  * update heights, return new root.  */ private avlnode < e > doublewithrightchild(avlnode < e > n1) {     n1.right = rotatewithleftchild(n1.right);     return rotatewithrightchild(n1); }  //updates height , balance factor private void updateheightandbf(avlnode < e > node) {     int leftheight, rightheight, bf = 0, height = 0;     if (node != null) {         if (node.getleft() == null) {             leftheight = -1;         } else {             leftheight = node.left.height;         }         if (node.getright() == null) {             rightheight = -1;         } else {             rightheight = node.right.height;         }         /*if (leftheight >= rightheight) {                 height = leftheight + 1;             } else if (rightheight >= leftheight) {                 height = rightheight + 1;             }*/         height = math.max(leftheight, rightheight) + 1;         bf = leftheight - rightheight;         node.setheight(height);         node.setbf(bf);     } else {         height = -1;     } }  /**  * private helper method.  * balances node updating balance  * factor when node removed  * or added avl tree.  *  * @param node node being balanced  */ private avlnode < e > balance(avlnode < e > node) {     int hleft, hright;     if (node == null) {         return node;     }     if (node.bf == 2) {         if (node.left.bf == 1) {             node.left = rotatewithleftchild(node);         } else if (node.left.bf == -1) {             node.left = doublewithleftchild(node);         }     } else if (node.bf == -2) {         if (node.right.bf < 0) {             node.right = rotatewithrightchild(node);         } else if (node.right.bf == -1) {             node.right = doublewithrightchild(node);         }     }     return node;  }  /**  * adds item tree.  duplicate items , null items should not added. o(log n)  *  * @param item item add  * @return true if item added, false if not  */  @override public boolean add(e item) { // todo     int thesize = size();     if (root == null && item != null) { //null check here item         root = new avlnode < e > (item);         count++;         return true;     } else if (item == null) {         return false;     } else {         add(root, item);         root = balance(root);     }     return (count != thesize); }  /**  * private helper method add() method.  * adds item tree.  duplicate items , null items should not added.  * runs in o(log n) expected time, may linear time in worst case  *  * @param value item add  * @return true if item added, false if not  */ private boolean add(avlnode < e > node, e value) { // todo     if (value.equals(node.getdata()) || value == null) {         //if it's duplicate or null         return false;     }     if (value.compareto(node.data) < 0) {         avlnode < e > left = node.left;         if (left == null) {             node.left = new avlnode < e > (value);             count++;             updateheightandbf(node);             balance(node);             return true;         } else updateheightandbf(node);         balance(node);         return add(left, value);     } else if (value.compareto(node.data) > 0) {         avlnode < e > right = node.right;         if (right == null) {             node.right = new avlnode < e > (value);             count++;             updateheightandbf(node);             balance(node);             return true;         } else {             updateheightandbf(node);             balance(node);             return add(right, value);         }     }     return false; }  /**  * returns maximum data held in tree. null if tree empty.  * runs in o(log n) expected, may linear in worst case  *  * @return maximum item or null if empty  */  @override public e max() {     if (isempty()) {         return null;     }     return max(root).data; }  /**  * private helper method max() method.  *  * @return maximum node or null if empty  */ private avlnode < e > max(avlnode < e > x) {     if (x.getright() == null) { //the rightmost node root         //is larger root, larger leftmost         //node root. so, if rightmost node null,         // means root node maximum data in tree         return x;     } else {         return max(x.getright());     } }  /**  * returns number of items in tree o(1) variable  *  * @return number of items in tree  */  @override public int size() {     return count; }  /**  * o(1)  * @return true if tree has no datas, false if tree has in it.  */  @override public boolean isempty() {     return size() == 0; }  /**  * runs in o(n) worst case, , o(log n) average case.  * @return minimum data in tree or null if empty  */  @override public e min() {     if (isempty()) {         return null;     }     return min(root).data; }  /**  * private helper method min() method  *  * @return minimum node in tree or null if empty  */ private avlnode < e > min(avlnode < e > y) {     if (y == null) {         return null;     } else if (y.left == null) { //the leftmost node root         //is smaller root, smaller rightmost         //node. so, if leftmost node null,         // means root node minimum data in tree         return y;     } else {         return min(y.left);     } }  /**  * checks given item in tree. o(log n)  *  * @param item item  * @return true if item in tree, false otherwise  */  @override public boolean contains(e item) {     return contains(root, item); }  /**  * private helper method contains() methods  * checks given item in tree.  * runs in o(log n) expected, may linear in worst case  *  * @param root starting point  * @param item item  * @return true if item in tree, false otherwise  */ private boolean contains(avlnode < e > root, e item) {     if (root == null || isempty()) {         return false;     }     if (item.compareto(root.getdata()) == 0) { //if item         //equal data in root node, return true         return true;     } else {         if (item.compareto(root.getdata()) < 0) { //if item less data             avlnode < e > left = root.getleft(); //go left node             return (contains(left, item)); //call contains() method left node         } else if (item.compareto(root.getdata()) > 0) { //if item more data             avlnode < e > right = root.getright(); //go right node             return (contains(right, item)); //call contains() method right node         } else {             return true;         }     } }  /**  * removes given item tree o(log n). if item found  * , removed, balance tree  *  * @param item item remove  * @return true if item removed, false if item not found  */  @override public boolean remove(e item) {     int thesize = size();     root = remove(root, item);     return (count != thesize); }  /**  * private helper method remove() method  * removes given item tree  * runs in o(log n) expected, may linear in worst case  * uses in-order successor  *  * @param node starting point  * @param item item remove  * @return node if specified node in tree, null otherwise  */ private avlnode < e > remove(avlnode < e > node, e item) { //todo     if (node == null || item == null) {         return null;     }     if (root == null) {         return root;     }     if (item.compareto(node.data) < 0) {         updateheightandbf(node);         balance(node);         node.left = remove(node.left, item);     } else if (item.compareto(node.data) > 0) {         updateheightandbf(node);         balance(node);         node.right = remove(node.right, item);     } else if (node.left != null && node.right != null) { //two child nodes         avlnode < e > succ = min(node.right);         node.data = succ.data;         updateheightandbf(node);         balance(node);         node.right = remove(node.right, node.data);     } else {         node = (node.left != null) ? node.left : node.right;         count--;         updateheightandbf(node);         return balance(node);     }     return node; }  /**  * runs in linear time, o(n)  * @return list of data in post-order traversal order  */  @override public list < e > getpostorder() {     list < e > postorderlist = new arraylist < e > (size());     recpostorder(root, postorderlist);     return postorderlist; }  /**  * private helper method getpostorder() method  * runs in linear time, o(n)  */ private void recpostorder(avlnode < e > theroot, list < e > thelist) {     if (theroot != null) {         recpostorder(theroot.left, thelist);         recpostorder(theroot.right, thelist);         thelist.add(theroot.data);     } }  /**  * runs in linear time, o(n)  * @return list of data in pre-order traversal order  */  @override public list < e > getpreorder() {     list < e > preorderlist = new arraylist < e > (size());     recpreorder(root, preorderlist);     return preorderlist;  }  /**  * private helper method getpreorder() method  * runs in linear time, o(n)  *  */ private void recpreorder(avlnode < e > theroot, list < e > thelist) {     if (theroot != null) {         thelist.add(theroot.getdata());         recpreorder(theroot.getleft(), thelist);         recpreorder(theroot.getright(), thelist);     } }  /**  * runs in linear time  * @return list of data in pre-order traversal order  */ public list < e > getinorder() {     list < e > inorderlist = new arraylist < e > (size());     recinorder(root, inorderlist);     return inorderlist; }  /**  *  * private helper method getinorder() method  * runs in linear time  *  */ private void recinorder(avlnode < e > theroot, list < e > thelist) {     if (theroot != null) {         recinorder(theroot.left, thelist);         thelist.add(theroot.data);         recinorder(theroot.right, thelist);     } }  /**  * runs in linear time, o(n)  * @return list of data in level-order traversal order  */  @override public list < e > getlevelorder() {     list < e > data = new arraylist < e > ();     queue < avlnode < e >> queue = new linkedlist < avlnode < e >> ();     if (this.isempty()) {         return data;     } else {         queue.add(root);     }     while (!queue.isempty()) {         avlnode < e > x = queue.remove();         if (x != null) {             data.add(x.getdata());             if (x.getleft() != null) {                 queue.add(x.getleft());             }             if (x.getright() != null) {                 queue.add(x.getright());             }         }     }     return data; }  /**  * o(1) [ignore garbage collection costs]  *  * removes datas tree  */  @override public void clear() {     root = null;     count = 0; }   /**  * returns iterator on collection  * iterator based on in-order traversal  */  @override public iterator < e > iterator() {     return new avliterator(); } }