# Clear order statistic (binary search) tree implementation

• The idea is the same as other posted BST solutions: view suffix of the array after position `i` as sorted, find `i`th element's rank within this suffix, and then have `i`th element join it to generate a new suffix.

``````public class Solution {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
int lcount;
int size;

TreeNode(int val) {
this.val = val;
size = 1;
}
}

TreeNode insert(TreeNode root, int val) {
if (root == null)
return new TreeNode(val);

root.size++; // for getting rank k element; not used in this problem
if (val < root.val) {
root.lcount++;
root.left = insert(root.left, val);
} else { // allows duplicate by having later ones on the right subtree
root.right = insert(root.right, val);
}

return root;
}

int rank(TreeNode root, int val) {
if (root == null) {
return 1; // as if the previously non-existent val gets inserted here
}

if (val == root.val)
return root.lcount + 1;
else if (val < root.val) {
return rank(root.left, val);
} else {
return rank(root.right, val) + root.lcount + 1;
}
}

public List<Integer> countSmaller(int[] arr) {
List<Integer> col = new ArrayList<>();
TreeNode root = null;
for (int i = arr.length - 1; i >= 0; i--) {