AVLTree.java

    import java.util.Stack;

    public class AVLTree<K extends Comparable<K>> {

        public static final int LEFT_HIGHER = -1;
        public static final int EQUAL_HEIGHT = 0;
        public static final int RIGHT_HIGHER = 1;
        private AVLNode<K> root;
        private Boolean taller;

        public AVLTree() {

            root = null;
            taller = true;
        }

        public void add(K input) {

            root = add(root, input);
        }

        private AVLNode<K> add(AVLNode<K> subroot, K input) {

            if (subroot == null) {

                subroot = new AVLNode<K>(input);
                this.taller = true;
            } else if (input.compareTo(subroot.data) == 0) {

                this.taller = false;
            } else if (input.compareTo(subroot.data) < 0) {

                subroot.left = add(subroot.left, input);
                if (this.taller) {

                    if (subroot.balance == LEFT_HIGHER) {

                        subroot = leftBalance(subroot);
                        taller = false;
                    } else if (subroot.balance == EQUAL_HEIGHT) {

                        subroot.balance = LEFT_HIGHER;
                    } else if (subroot.balance == RIGHT_HIGHER) {

                        this.taller = false;
                        subroot.balance = EQUAL_HEIGHT;
                    }
                }
            } else {

                subroot.right = add(subroot.right, input);
                if (this.taller) {

                    if (subroot.balance == LEFT_HIGHER) {

                        taller = false;
                        subroot.balance = EQUAL_HEIGHT;
                    } else if (subroot.balance == EQUAL_HEIGHT) {

                        subroot.balance = RIGHT_HIGHER;
                    } else if (subroot.balance == RIGHT_HIGHER) {

                        subroot = rightBalance(subroot);
                        taller = false;
                    }
                }
            }

            return subroot;
        }

        public AVLNode<K> leftBalance(AVLNode<K> subroot) {

            AVLNode<K> leftTree = subroot.left;
            AVLNode<K> subTree = null;
            if (leftTree.balance == LEFT_HIGHER) {

                subroot.balance = EQUAL_HEIGHT;
                leftTree.balance = EQUAL_HEIGHT;
                subroot = rotateRight(subroot);
                this.taller = false;
            }
            if (leftTree.balance == RIGHT_HIGHER) {

                subTree = leftTree.right;
                subTree.balance = EQUAL_HEIGHT;
                leftTree = rotateLeft(leftTree);
                subroot.left = leftTree;
                subroot = rotateRight(subroot);

                if (subTree.balance == EQUAL_HEIGHT) {

                    subroot.balance = EQUAL_HEIGHT;
                    leftTree.balance = EQUAL_HEIGHT;
                } else if (subTree.balance == LEFT_HIGHER) {

                    subroot.balance = EQUAL_HEIGHT;
                    leftTree.balance = LEFT_HIGHER;
                } else {

                    subroot.balance = RIGHT_HIGHER;
                    leftTree.balance = EQUAL_HEIGHT;
                }
            }

            return subroot;
        }

        public AVLNode<K> rightBalance(AVLNode<K> subroot) {

            AVLNode<K> rightTree = subroot.right;
            AVLNode<K> subTree = null;
            if (rightTree.balance == RIGHT_HIGHER) {

                subroot.balance = EQUAL_HEIGHT;
                rightTree.balance = EQUAL_HEIGHT;
                subroot = rotateLeft(subroot);
            }
            if (rightTree.balance == LEFT_HIGHER) {

                subTree = rightTree.left;
                subTree.balance = EQUAL_HEIGHT;
                rightTree = rotateRight(rightTree);
                subroot.right = rightTree;
                subroot = rotateLeft(subroot);

                if (subTree.balance == EQUAL_HEIGHT) {

                    subroot.balance = EQUAL_HEIGHT;
                    rightTree.balance = EQUAL_HEIGHT;
                } else if (subTree.balance == LEFT_HIGHER) {

                    subroot.balance = EQUAL_HEIGHT;
                    rightTree.balance = RIGHT_HIGHER;
                } else {

                    subroot.balance = LEFT_HIGHER;
                    rightTree.balance = EQUAL_HEIGHT;
                }
            }

            return subroot;
        }

        private AVLNode<K> rotateLeft(AVLNode<K> subroot) {

            AVLNode<K> rightSubTree = subroot.right;
            subroot.right = rightSubTree.left;
            rightSubTree.left = subroot;
            return rightSubTree;
        }

        private AVLNode<K> rotateRight(AVLNode<K> subroot) {

            AVLNode<K> leftSubTree = subroot.left;
            subroot.left = leftSubTree.right;
            leftSubTree.right = subroot;
            return leftSubTree;
        }

        public int getHeight(AVLNode<K> subroot) {

            if (subroot == null)
                return 0;
            if (subroot.left == null && subroot.right == null)
                return 1;
            int hl = subroot.left != null ? getHeight(subroot.left) : 0;
            int hr = subroot.right != null ? getHeight(subroot.right) : 0;
            return hl > hr ? hl + 1 : hl + 1;
        }

        // copy from binary tree
        public void toDot() {
            AVLNode<?> n;
            // create a variable to contain result
            String dot = "graph BinaryTree {\n";
            Stack<AVLNode<?>> stack = new Stack<AVLNode<?>>();

            // begin with root
            n = root;
            stack.push(n);
            do {
                // append current node to result
                dot += n.toDot();
                // now if current node has childs and wed add it to queue for
                // parsing later
                if (n.left != null) {
                    stack.push(n.left);
                }
                if (n.right != null) {
                    stack.push(n.right);
                }
                n = stack.pop();
            } while (!stack.empty());
            // tree traversal with NO recursion ! cool huh? instead of the call
            // stack we use a stack.
            // Question for you is, am I using depth 1st or breath 1st traversal?
            // Answer: this is breath 1st because it parse all the child nodes in
            // same level before move to next level
            System.out.print(dot + "\n}");
        }
    }