Trouble rebalancing the root node of an AVL tree <p>Hello guys i seem to be having trouble rebalancing the AVL tree. It balances everything else except the root node. I don't know why it doesn't balance the root node. When i pass values such as 50, 40, 30, 20, and 10. I get 50,30, 20, 10 and 40. 50 should not be the root, the correct root value should be 40. Below is my code:</p> <pre><code>public void insert(T data){ AVLNode&lt;T&gt; newNode = new AVLNode&lt;T&gt;(data); if(isEmpty()){ root = newNode; } else{ insert(root, newNode); } } private void insert(AVLNode&lt;T&gt; root, AVLNode&lt;T&gt; newNode){ if(newNode.getData().compareTo(root.getData())&lt;0){ if(root.getLeftChild()!=null){ AVLNode&lt;T&gt; leftNodes = root.getLeftChild(); insert(leftNodes, newNode); root.setLeftChild(rebalance(leftNodes)); } else{ root.setLeftChild(newNode); } } else if(newNode.getData().compareTo(root.getData())&gt;0){ if(root.getRightChild()!=null){ AVLNode&lt;T&gt; rightNodes = root.getRightChild(); insert(rightNodes, newNode); root.setRightChild(rebalance(rightNodes)); } else{ root.setRightChild(newNode); } } else{ root.setData(newNode.getData()); } updateHeight(root); } //re-balances the tree. private AVLNode&lt;T&gt; rebalance(AVLNode&lt;T&gt; root){ int difference = balance(root); if (difference &gt; 1){ if(balance(root.getLeftChild())&gt;0){ root = rotateRight(root); } else{ root = rotateLeftRight(root); } } else if(difference &lt; -1){ if(balance(root.getRightChild())&lt;0){ root = rotateLeft(root); } else{ root = rotateRightLeft(root); } } return root; } //updates the height of the tree. public void updateHeight(AVLNode&lt;T&gt; root){ if((root.getLeftChild()==null) &amp;&amp; (root.getRightChild()!=null)){ root.setHeight(root.getRightChild().getHeight()+1); } else if((root.getLeftChild() !=null)&amp;&amp;(root.getRightChild()==null)){ root.setHeight(root.getLeftChild().getHeight()+1); } else root.setHeight(Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()))+1); } private int balance(AVLNode&lt;T&gt; root) { return getHeight(root.getLeftChild())-getHeight(root.getRightChild()); } //single left left rotation of the tree private AVLNode&lt;T&gt; rotateLeft(AVLNode&lt;T&gt; root){ AVLNode&lt;T&gt; NodeA = root.getRightChild(); root.setRightChild(NodeA.getLeftChild()); NodeA.setLeftChild(root); root.setHeight(Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()))+1); //updates the height NodeA.setHeight(Math.max(getHeight(NodeA.getLeftChild()), getHeight(NodeA.getRightChild()))+1); return NodeA; } //single right right rotation of the tree private AVLNode&lt;T&gt; rotateRight(AVLNode&lt;T&gt; root){ AVLNode&lt;T&gt; NodeA = root.getLeftChild(); root.setLeftChild(NodeA.getRightChild()); NodeA.setRightChild(root); root.setHeight(Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()))+1); //updates the height of the AVL tree NodeA.setHeight(Math.max(getHeight(NodeA.getLeftChild()), getHeight(NodeA.getRightChild()))+1); return NodeA; } //a double rotation. Left right rotation private AVLNode&lt;T&gt; rotateLeftRight(AVLNode&lt;T&gt; root){ AVLNode&lt;T&gt; nodeA = root.getLeftChild(); root.setLeftChild(rotateLeft(nodeA)); return rotateRight(root); } //a right left rotation private AVLNode&lt;T&gt; rotateRightLeft(AVLNode&lt;T&gt; root){ AVLNode&lt;T&gt; nodeA = root.getRightChild(); root.setRightChild(rotateRight(nodeA)); return rotateLeft(root); } </code></pre>