private Node insert(Node root, int data,int count[],int pos,int val){
        if(root == null){
            count[pos] = val;
            return Node.newNode(data);
        }
        if(root.data <= data){
            val++;
            if(root.left != null){
                val += root.left.size;
            }
            root.right = insert(root.right,data,count,pos,val);
        }
        else{
            root.left = insert(root.left,data,count,pos,val);
        }
        if(height(root.left) - height(root.right) > 1){
            if(height(root.left.left) >= height(root.left.right)){
                root = rightRotate(root);
        }else{
                root.left = leftRotate(root.left);
                root = rightRotate(root);
            }
        }else if(height(root.right) - height(root.left) > 1){
            if(height(root.right.right) >= height(root.right.left)){
                root = leftRotate(root);
            }else{
                root.right = rightRotate(root.right);
                root = leftRotate(root);
            }
        }
        else{
            root.height = setHeight(root);
            root.size = setSize(root);
        }
        return root;
    }
http://www.geeksforgeeks.org/count-smaller-elements-on-right-side/
Test cases
All same elements
Many duplicates
Negative numbers
0s
Sorted or reverse sorted
src/com/interview/tree/CountNumberOfSmallerElementOnRight.java