self-balancing avl tree
<p>I am trying to do a an avl tree which updates itself everytime the tree is unbalanced. The rotations are working but i have a bug where if for example the tree node 7, leftChild 6 , leftchild of leftchild 5 becomes node 6, leftchild 5, rightchild 7, and after balancing I add a new node, the node is first compared with 7 and not with 6. How do I fix this problem?</p>

<p>This is the main class:</p>

<pre><code>import java.io.*;
import javax.swing.*;
import java.util.*;
import java.lang.*;

public class NewMain  implements Cloneable{

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {

        File file = new File ("AVLTree.txt");
        ArrayList &lt;TreeNode&gt; array = new ArrayList ();
        Scanner kb = new Scanner (System.in);
        int num = 0;
        TreeNode root = new TreeNode ();
        do {
            System.out.print("              AVL Tree            \n\n\n\n");
            System.out.println("1. Create a new binary tree");
            System.out.println("2. Save Tree");
            System.out.println("3. Load Tree");
            System.out.println("4. Enter a new node in the tree");
            System.out.println("5. Show current AVL tree");
            System.out.println("6. Show inorder traversal");
            System.out.println("7. Search");
            System.out.println("8. Quit  \n\n\n\n\n\n\n");
            System.out.print("Enter a number: ");
            num = kb.nextInt ();
            if (num == 1){
                if (array.isEmpty ())
                {
                    System.out.print ("Enter the root value: ");
                    int value = kb.nextInt ();
                    root = new TreeNode();
                    root.setValue(value);
                    array.add(root);
                }
                else
                {
                    array.clear();
                    System.out.print ("Enter the root value: ");
                    int value = kb.nextInt ();
                    root = new TreeNode();
                    root.setValue(value);
                    array.add(root);
                }
            }
            if (num == 2) 
            {
                    FileOutputStream outFile = null;
                    ObjectOutputStream oos = null;
                    try 
                    {
                        outFile = new FileOutputStream(file);             
                        oos = new ObjectOutputStream(outFile);
                        for (TreeNode list : array) 
                        {                 
                            oos.writeObject(list);                                      
                        }
                        oos.close();
                    }
                    catch (Exception e) 
                    {
                        System.out.print("Save Not Successful!");
                    }
               }
            if (num == 3) 
            {
                if (file.exists()) 
                {
                    FileInputStream inFile = null;
                    ObjectInputStream ios = null;
                    try 
                    {
                        Object obj = null;
                        inFile = new FileInputStream(file); 
                        ios = new ObjectInputStream(inFile); 
                        while ((obj = ios.readObject()) != null) {              
                            if (obj instanceof TreeNode) 
                            { 
                                array.add((TreeNode) obj);
                            }
                        }
                        ios.close(); 
                    } 
                    catch(EOFException e)
                    {   
                    }
                    catch (Exception e) 
                    {
                        System.out.print("File was not found while loading");
                    }
                }
            }
            if (num == 4)
            {
                System.out.print ("Enter a new child node: ");
                int value = kb.nextInt ();              
                try 
                {
                    array.add(root.insert(value));  
                    root.balance();
                }
                catch (Exception e)
                {
                    System.out.print (e.getMessage());
                }

            }
            if (num == 5){
                System.out.print ("Pointer Number\t\tLeft\t\tNode\t\tRight\t\tLeft Height\t\tRight Height\n");
                for (int i=0; i&lt;array.size();i++)
                {                     
                      System.out.print (i+"\t\t\t"+array.indexOf(array.get(i).getLeftChild())+"\t\t"+array.get(i).getValue()+"\t\t"+array.indexOf(array.get(i).getRightChild())+"\t\t"+array.get(i).getLeftHeight()+"\t\t\t"+array.get(i).getRightHeight()+"\n");
                }
            }
            if (num == 6)
            {
                System.out.print("Inorder traversal: ");
                System.out.println(root.InOrderTraversal());
                System.out.print("Postorder traversal: ");
                System.out.println(root.PostOrderTraversal());
                System.out.print("Preorder traversal: ");
                System.out.println(root.PreOrderTraversal());
            }
            if (num == 7)
            {
                System.out.print("Enter node to be searched: ");
                int node = kb.nextInt ();
                for (int i = 0; i&lt;array.size();i++)
                {
                    if (node == array.get(i).getValue())
                    {
                        System.out.print ("Node is in index "+i+"\n");
                        break;
                    }
                    if (i == array.size()-1 &amp;&amp; node != array.get(i).getValue())
                    {
                        System.out.print ("Node not found in the tree!"+"\n");
                        break;
                    }
                }

            }            
        }while (num != 8);
    }
}
</code></pre>

<p>This is from a normal java class:</p>

<pre><code>import java.lang.StringBuilder;
import java.util.ArrayList;
import java.io.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.swing.*;
public class TreeNode implements Serializable, Cloneable
{
    public Integer value;
    public TreeNode leftChild;
    public TreeNode rightChild;

    public TreeNode()
    {
        this.value = null;
        this.leftChild = null;
        this.rightChild = null;
    }

    public TreeNode(int value)
    {
        this.value = value;
        this.leftChild = null;
        this.rightChild = null;
    }

    public int getValue()
    {
        return this.value;
    }

    public void setValue(int value)
    {
        this.value = value;
    }

    public TreeNode getLeftChild()
    {
        return this.leftChild;
    }

    public void setLeftChild(TreeNode leftChild)
    {
        this.leftChild = leftChild;
    }

    public TreeNode getRightChild()
    {
        return this.rightChild;
    }

    public void setRightChild(TreeNode rightChild)
    {
        this.rightChild = rightChild;        
    }

    public int getLeftHeight()
    {
        if (this.leftChild == null)
        {
            return 0;
        }
        else
        {    
            return this.getLeftChild().getHeight() + 1;
        }

    }

    public int getRightHeight()
    {
        if (this.rightChild == null)
        {
            return 0;
        }
        else
        {
            return this.getRightChild().getHeight() + 1;
        }
    }

    public TreeNode insert(int value) throws Exception
    {
      if(this.value == null &amp;&amp; this.leftChild == null &amp;&amp; this.rightChild == null)
      {
            this.value = value;
            return this;
      }
        else
        {
            TreeNode node = new TreeNode (value);
            if(value &lt; this.value)
            {
                if(this.getLeftChild() == null)
                {
                    this.setLeftChild (node);
                    return node;
                }
                else
                {
                    return this.getLeftChild().insert(value);
                }
            }
            else if(value &gt; this.value)
            {
                if(this.getRightChild() == null)
                {
                    this.setRightChild(node);
                    return node;
                }

                else
                {
                    return this.getRightChild().insert(value);
                }

            }
            else 
            {
                return null;
            }
        } 

    }
    public TreeNode balance() throws Exception
    {
        if (Math.abs(this.getLeftHeight() - this.getRightHeight())==2)
        {
            if (this.rightChild == null)
            {
                if(this.leftChild.leftChild != null)
                { 
                    return this.LLRotation ();
                }
                if(this.leftChild.rightChild != null)
                { 
                    return this.LRRotation ();
                }
            }
            if (this.leftChild == null)
            {
                if (this.rightChild.rightChild != null)
                {
                    return this.RRRotation ();
                }
                if (this.rightChild.leftChild != null)
                {
                    return this.RLRotation ();
                }
            }
        }
        else
        {
            if (this.getLeftChild () != null)
            {
                return this.getLeftChild().balance();
            }
            if (this.getRightChild () != null)
            {
                return this.getRightChild().balance();
            }
        }
        return this;
    }
    public int getHeight ()
    {
        if (this.leftChild == null &amp;&amp; this.rightChild == null)
        {
            return 0;
        }
        else
        {
            int leftH = 0;
            int rightH = 0;
            if (this.leftChild != null)
            {
                leftH++;
                leftH += this.getLeftChild().getHeight();
            }
            if (this.rightChild != null)
            {
                rightH++;
                rightH += this.getRightChild().getHeight();
            }
            return Math.max(leftH,rightH);
        }
    }

    public TreeNode LLRotation ()
    {
        TreeNode temp = this.leftChild;
        this.leftChild = null;
        temp.rightChild = this;
        return temp;
    }

    public TreeNode RRRotation ()
    {  
        TreeNode temp = this.rightChild;
        this.rightChild = temp.leftChild;
        try 
        {
            temp.leftChild = (TreeNode)this.clone();
        } 
        catch (CloneNotSupportedException ex) 
        {
        }
        this.value = temp.value;
        this.rightChild = temp.rightChild;
        this.leftChild = temp.leftChild;
        return temp;
    }

    public TreeNode LRRotation ()
    {
        this.leftChild = this.leftChild.RRRotation();
        return LLRotation();
    }

    public TreeNode RLRotation ()
    {
        this.rightChild = this.rightChild.RRRotation();
        return RRRotation();
    }

    public String InOrderTraversal ()
    {
        StringBuilder sb = new StringBuilder ();
        if (this.leftChild == null &amp;&amp; this.rightChild == null)
        {
            sb.append(this.value).append(" ");
        }
        else
        {
            if(this.leftChild != null)
            {
                sb.append(this.getLeftChild().InOrderTraversal());
            }
            sb.append(this.value).append(" ");

            if (this.rightChild != null)
            {
                sb.append(this.getRightChild().InOrderTraversal());
            }
        }
        return sb.toString();
    }
    public String PostOrderTraversal ()
    {
        StringBuilder sb = new StringBuilder ();
        if (this.leftChild == null &amp;&amp; this.rightChild == null)
        {
            sb.append(this.value).append(" ");
        }
        else
        {
            if(this.leftChild != null)
            {
                sb.append(this.getLeftChild().PostOrderTraversal());
            }
            if (this.rightChild != null)
            {
                sb.append(this.getRightChild().PostOrderTraversal());
            }
            sb.append(this.value).append(" ");
        }
        return sb.toString();
    }
    public String PreOrderTraversal ()
    {
        StringBuilder sb = new StringBuilder ();
        if (this.leftChild == null &amp;&amp; this.rightChild == null)
        {
            sb.append(this.value).append(" ");
        }
        else
        {
            sb.append(this.value).append(" ");
            if(this.leftChild != null)
            {
                sb.append(this.getLeftChild().PreOrderTraversal());
            }
            if (this.rightChild != null)
            {
                sb.append(this.getRightChild().PreOrderTraversal());
            }
        }
        return sb.toString();
    }
}
</code></pre>
