Count smaller elements on right side in a given Array.

eg : [4,12,5,6,1,34,3,2]
o/p  [3,5, 3,3,0, 2,1,0]


ex2: {8, 3, 10, 1, 6, 14, 4, 7, 13}
o/p: {5, 1, 4,  0, 1, 3,  0, 0, 0}


Approach:
Example array: A: [4,12,5,6,1,34,3,2]
1. Start creating BST from the end of the array.


tree node is like:
class Node {
Integer data;
Integer left_count;
Integer counter;
Node left;
Node right;

public Node(Integer data) {
this.data = data;
this.left_count = 1;
this.counter = 0;
this.left = null; this.right = null;
}
}


2. every tree node has left_count (size of left subtree + 1) and counter (number of smaller elements on the right side.)


3. Recursion looks like this:
public static Node insertIntoBST(Node node, int value, int leftSum) {
if (null == node) { return new Node(value); }
if (value <= node.data) {
++node.left_count;
node.left = insertIntoBST(node.left, value,leftSum);
if (node.left.left == null && node.left.right == null)
node.left.counter = leftSum;
} else {
node.right = insertIntoBST(node.right, value, node.left_count+leftSum);
if (node.right.right == null && node.right.left == null)
node.right.counter = node.left_count+node.counter;
}
return node;
}

4. Lets trace the above code with example:
A: [4,12,5,6,1,34,3,2]


start inserting from the end of the array A.
So ..
step1: insert (2) - its the root node.
       2 (1,0) -> 1 is left_count and 0 is counter.
  

step2: insert (3) - it will go to right of 2
  2 (1,0)
   3(1,1)


step3: insert (34) - it will go to right of 3
2 (1,0)
     3(1,1)
        34(1,2)
step4: insert (1) - it will go to the left of 2.
2(2,0)
1(1,0) 3(1,1)
                  `34(1,2)


step5: insert (6) - it will go to the left of 34.
2(2,0)
1(1,0) 3(1,1)
                  34(1,2)
        6(1,3)

step6: insert (5) - it will go to the left of 6.
2(2,0)
1(1,0) 3(1,1)
          34(1,2)
    6(2,3)
5(1,3)

step7: insert (12) - it will go to the right of 12.
2(2,0)
1(1,0) 3(1,1)
34(1,2)
6(2,3)
5(1,3) 12(1,5)

step8: insert (4) - it will go to the left of 5.
2(2,0)
1(1,0) 3(1,1)
                34(1,2)
       6(3,3)
         5(2,3) 12(1,5)
     4(1,3)

4 has counter 3 because from root we take right so leftsum is now 2, again we take right from 3, so leftsum+=1 = 3, and from 34 we keep left till we insert it has left child of 5.
We are done!


Code input/ouput:
eg : [4,12,5,6,1,34,3,2]
o/p  [3,5, 3,3,0, 2,1,0]
Printing data and count of smaller elements to the right: 
1::0
2::0
3::1
4::3
5::3
6::3
12::5
34::2


ex2: {8, 3, 10, 1, 6, 14, 4, 7, 13}
o/p: {5, 1, 4,  0, 1, 3,  0, 0, 0}
Printing data and count of smaller elements to the right: 
1::0
3::1
4::0
6::1
7::0
8::5
10::4
13::0
14::3

Time complexity: O(nlogn)