Generating unique positive integer numbers and adding them to AVL Tree

Question

I am trying to generate and insert 1000 unique positive integer numbers to an AVL Tree with the size of 1000. These positive numbers have no upper bound.But for convenience, İ gave the upper bound Integer.MAX_VALUE.My problem is, i can add 1000 numbers to arraylist but when i try to add numbers from arraylist to avl tree, it only adds some of those numbers(i.e., 39 out 1000 numbers) and i spent a day to solve it. Any help is appreciated.

This is my AVL Tree class:

import java.util.Stack;

public class AVLTree {

    public int findHeight(AVLNode node){
        if(node != null)
            return node.height;
        return 0;
    }
    public int getBalance(AVLNode node){
        if(node != null)
            return findHeight(node.left) - findHeight(node.right);
        return 0;
    }
    public AVLNode insertNumber(AVLNode node, int data){
        if(node == null) {
            return (new AVLNode(data));
        }
        //If current node's number is greater than newly added node's number, add it to the right
        if(node.number < data){
            node.right = insertNumber(node.right,data);
        }
        //If current node's number is less greater than newly added node's number, add it to the left
        else{
            node.left = insertNumber(node.left,data);
        }

        //update node's height
        node.height = Math.max(findHeight(node.left), findHeight(node.right)) + 1;
        int balDiff = getBalance(node);

        // Left Rotate
        if (balDiff > 1 && data < node.left.number) {
            return rotateRight(node);
        }

        // Right Rotate
        if (balDiff < -1 && data > node.right.number) {
            return rotateLeft(node);
        }

        // Left Right Rotate
        if (balDiff > 1 && data > node.left.number) {
            node = rotateLeft(node.left);
            return rotateRight(node);
        }

        // Right Left Rotate
        if (balDiff < -1 && data < node.right.number) {
            node = rotateRight(node.right);
            return rotateLeft(node);
        }
        return node;
    }
    public AVLNode rotateRight(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;

        // Rotation
        x.right = y;
        y.left = T2;

        // update their heights
        x.height = Math.max(findHeight(x.left), findHeight(x.right)) + 1;
        y.height = Math.max(findHeight(y.left), findHeight(y.right)) + 1;

        return x;
    }
    public AVLNode rotateLeft(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;

        // Rotation
        y.left = x;
        x.right = T2;

        // update their heights
        x.height = Math.max(findHeight(x.left), findHeight(x.right)) + 1;
        y.height = Math.max(findHeight(y.left), findHeight(y.right)) + 1;

        return y;
    }
    public void printInorder(AVLNode root){
        if(root != null){
            printInorder(root.left);
            System.out.println(root.number);
            printInorder(root.right);
        }
    }
    public int findMaximum(AVLNode node){
        //Recursive solution
        /*if(node.right == null) {
            return node.number;
        } else {
            return findMaximum(node.right);
        }*/

        //Iterative solution
        while(node.right != null){
            node = node.right;
        }
        return node.number;
    }
    public int findMinimum(AVLNode node){
        //Recursive solution
        /*
        if(node.left == null)
            return node.number;
        else
            return findMinimum(node.left);
        */

        //Iterative solution
        while(node.left != null){
            node = node.left;
        }
        return node.number;
    }
    public double getSum(AVLNode node){
        if(node == null)
            return 0;
        return node.number + getSum(node.left) + getSum(node.right);
    }
    public int getSumSmaller(AVLNode root, int data){
        int sum = 0;
        Stack<AVLNode> s1 = new Stack<AVLNode>();
        Stack<AVLNode> s2 = new Stack<AVLNode>();
        s1.push(root);

        while(!s1.isEmpty()){
            AVLNode tmp = s1.pop();
            s2.push(tmp);

            if(tmp.left != null && tmp.left.number < data){
                s1.push(tmp.left);
                sum = sum + tmp.left.number;
            }
            if(tmp.right != null && tmp.right.number < data){
                s1.push(tmp.right);
                sum = sum + tmp.right.number;
            }
        }
        return sum;
    }
}

And this is my Main Java class:

public static void main(String[] args) {
        Random rnd = new Random();
        ArrayList<Integer> ar = new ArrayList<>();
        int counter = 0;
        AVLNode root = null;
        AVLTree avltree1 = new AVLTree();
        //AVLTree avltree2 = new AVLTree();
        //AVLTree avltree3 = new AVLTree();

        while(counter < 1000) {
            int val;
            do{
                val = rnd.nextInt(Integer.MAX_VALUE);
            }while(ar.contains(val));
            ar.add(val);
        }

        long initTime = System.nanoTime();
        for(int i = 0;i < counter;i++){
            root = avltree1.insertNumber(root,ar.get(i));
        } 
        long finishTime = System.nanoTime();
        avltree1.printInorder(root);
        long durationTime = finishTime-initTime;
}

Answer 1

One problem I can see straight away is that the loop

while(counter < 1000) {
    int val;
    do{
        val = rnd.nextInt(Integer.MAX_VALUE);
    }while(ar.contains(val));
    ar.add(val);
}

never terminates, because the variable counter is not incremented.

You have bigger problems in your AVLTree.insert() method. Take the following code:

// Right Left Rotate
if (balDiff < -1 && data < node.right.number) {
    node = rotateRight(node.right); // node = node.right.left;
    return rotateLeft(node); // return node.right
}

If root is the original node, then this piece of code will return root.right.left.right. So in the loop

for(int i = 0;i < counter;i++){
    root = avltree1.insertNumber(root,ar.get(i));
} 

the value of root will occasionally move deeper into the tree. No wonder then that when you call printInorder(root);, it only prints part of the tree.

That isn't your only problem. To find out a bit more about what's going on, I recommend creating a more useful method to display the tree:

public void printOut(AVLNode root)
{
  System.out.print("(");
  if (root != null) {
    System.out.print(root.number);
    printOut(root.left);
    printOut(root.right);
  }
  System.out.print(")");
}

Then modify your original loop to

for(int i = 0;i < counter;i++){
    root = avltree1.insertNumber(root,ar.get(i));
    avltree1.printOut(root);
} 

Reduce the size of the tree down from 1000 to get an idea of what's going on. You might like to keep track of the original root and call printOut(originalRoot); in the loop as well.