Trouble implementing avl tree in java

Question

Hello guys i have been trying to implement an AVL tree but not succeeding. I am practicing to get the concept. So far i have succeeded in inserting to the tree, get the height of the tree, check to see if it's balanced, number of nodes in tree, find min and Max values in three, and check if a value is in the tree. Now i'm trying to balanced the tree while inserting a new node in the tree but having no success. Please could you guide me in what i did wrong. Below is my code with my result. Please bear with and thanks. Below is my node class: BinaryNode.java

public class BinaryNode<T> {

private T data;
private BinaryNode<T> rightChild;
private BinaryNode<T> leftChild;

public BinaryNode(){}

public BinaryNode(T data){
    this(data, null, null);
}
public BinaryNode(T data, BinaryNode<T> leftChild, BinaryNode<T> rightChild){
    this.data = data;
    this.leftChild = leftChild;
    this.rightChild = rightChild;
}

public void setLeftChild(BinaryNode<T> leftChild){
    this.leftChild = leftChild;
}

public void setRightChild(BinaryNode<T> rightChild){
    this.rightChild = rightChild;
}
public BinaryNode<T> getRightChild() {
    return rightChild;
}
public BinaryNode<T> getLeftChild() {
    return leftChild;
}

public T getData(){
    return data;
}
public int Height(){
    return getHeight(this);
}
//returns the height of the tree
private int getHeight(BinaryNode<T> root){
    if(root == null){
        return -1;
    }
    else
        return 1+Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()));
}

//functions get the number of nodes availabe in the tree
protected int getNumberOfNodes(){
   int a=0,b=0;
   if(leftChild!=null){
       a = leftChild.getNumberOfNodes();
           }

       if(rightChild!=null){
       b = rightChild.getNumberOfNodes();
       }
   return a+b+1;
}

 public void balance(){
   balance(this);
 }
private void balance(BinaryNode<T> root){
   int balance = getHeight(root.getLeftChild())-getHeight(root.getRightChild());
   if(balance>2){
       if(getHeight(root.getLeftChild())>=getHeight(root.getRightChild())){
           rotateRight(root);
       }
       else{
           doubleRotateRight(root);
       }
   }
   else if(balance<-2){
       if(getHeight(root.getRightChild())>=getHeight(root.getLeftChild())){
           rotateLeft(root);
       }
       else{
           doubleRotateLeft(root);
       }
   }
   else{
       getHeight(root);
   }
 }
//right right rotation
private BinaryNode<T> rotateRight(BinaryNode<T> root){
    BinaryNode<T> nodeA = root.getLeftChild();
    root.setLeftChild(nodeA.getRightChild());
    nodeA.setRightChild(root);
    return nodeA;
}

//left left rotation
private BinaryNode<T> rotateLeft(BinaryNode<T> root){
    BinaryNode<T> nodeA = root.getRightChild();
    root.setRightChild(nodeA.getLeftChild());
    nodeA.setLeftChild(root);
    return nodeA;
}

//right left rotation
private BinaryNode<T> doubleRotateLeft(BinaryNode<T> root){
    BinaryNode<T> nodeA = root.getLeftChild();
    root.setRightChild(rotateRight(nodeA));
    return rotateLeft(root);
}
//left right rotation
private BinaryNode<T> doubleRotateRight(BinaryNode<T> root){
    BinaryNode<T> nodeA = root.getRightChild();
    root.setLeftChild(rotateLeft(nodeA));
    return rotateRight(root);
}


}

BinarySearchTree:

public class BinarySearchTree<T extends Comparable<? super T>> {

private BinaryNode<T> root;

public BinarySearchTree() {}

public BinarySearchTree(T data){
    root = new BinaryNode<T>(data);
}

public void insert(T data){

    BinaryNode<T> newNode = new BinaryNode<T>(data);
    if(isEmpty()){
        root = newNode;
    }
    else
        insertElements(root, newNode);
}
private void insertElements(BinaryNode<T> root, BinaryNode<T> newNode){
    if(newNode.getData().compareTo(root.getData())<0){
        if(root.getLeftChild()==null){
            root.setLeftChild(newNode);
        }
        else
            insertElements(root.getLeftChild(), newNode);
            //balance(root.getLeftChild());
    }
    else{
        if(root.getRightChild()==null){
            root.setRightChild(newNode);
        }
        else{
            insertElements(root.getRightChild(), newNode);
            //balance(root.getRightChild()); 
        }
    }
    balance(root);
}
public void balance(BinaryNode<T> root){
    root.balance();
}
public boolean isEmpty(){
    return (root==null);
}

public void preOrder(){
    preOrder(root);
}

private void preOrder(BinaryNode<T> root){
    if(root == null){
        return;
    }
    else{
        System.out.println(root.getData());
        preOrder(root.getLeftChild());
        preOrder(root.getRightChild());
    }
}
public int getHeight(){
    return root.Height();
}
//gets the number of nodes in the tree
public int getNumberOfNodes(){
    return root.getNumberOfNodes();
}
//returns true or false if tree is balanced
 public boolean isBalanced(){
       if(root==null){
           return true;
       }
           if(checkHeight(root)==-1){
               return false;
           }
           else{
               return true;
       }
   }

 //checks to see if the tree is balanced. 
 private int checkHeight(BinaryNode<T> root){
     if(root==null){
         return 0;
     }
     int left = checkHeight(root.getLeftChild());
     int right = checkHeight(root.getRightChild());
     if(left==-1||right==-1){
         return -1;
     }
     if(Math.abs(left-right)>1){
         return -1;
     }
     else
         return Math.max(left, right)+1;
 }
 public T findMin(){
     return findMin(root);
 }

 private T findMin(BinaryNode<T> root){
     if(root==null){
         return null;
     }
     else if(root.getLeftChild()==null){
         return root.getData();
     }
     else
         return findMin(root.getLeftChild());

 }
 public T findMax(){
     return findMax(root);
 }
 private T findMax(BinaryNode<T> root){
     if(root==null){
         return null;
     }
     else if(root.getRightChild()==null){
         return root.getData();
     }
     else return findMax(root.getRightChild());
 }

 public boolean contains(T entry){
     return contains(root, entry);
 }
 private boolean contains(BinaryNode<T> root, T entry){
    if(root == null){
        return false;
    }
    else if(entry.compareTo(root.getData())<0){
        return contains(root.getLeftChild(), entry);
    }
    else if(entry.compareTo(root.getData())>0){
        return contains(root.getRightChild(), entry);
    }
    else{
        if(entry.compareTo(root.getData())==0){
        return true;
        }
        else
            return false;
    }

 }
 public void makeEmpty(){
     this.root = null;
  }
}

Test class:

public class Test {

public static void main(String[] args) {
    // TODO Auto-generated method stub
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.insert(5);
        tree.insert(10);
        tree.insert(20);

        tree.preOrder(); //prints out the tree in a pre-order list

        System.out.println("Height of tree: " +tree.getHeight());
        System.out.println("Number of Nodes: "+tree.getNumberOfNodes());
        System.out.println("Balanced: "+tree.isBalanced());
        System.out.println("Find max:  "+ tree.findMax());
        System.out.println("Find min: "+tree.findMin());
        System.out.println("Contains: "+tree.contains(1));
 }
}

Below is the result. But i am wrong as the tree is not balanced. There seems to be something wrong. As every time i insert a new node i also balance the try to balance the tree. Please could someone help me out and detect what i'm doing wrong. I do apologize if the code is lengthy. Result:

5
10
20
Height of tree: 2
Number of Nodes: 3
Balanced: false
Find max:  20
Find min: 5
Contains: false

Answer 1

Your method BinarySearchTree#checkHeight(BinaryNode<T> root) reports that the tree is out of balance if the heights of the left and right subtrees differ by more than one. However, when you insert a node, it eventually calls the method BinaryNode#balance(BinaryNode<T> root), which will not rotate nodes unless the subtree heights differ by more than 2. You need to modify the latter method to rotate nodes when the heights differ by more than 1. Also, the call to getHeight(root) in the else case of that method seems useless.

There may be other problems, but that's the only one that I saw.