Count of Smaller Numbers After Self

TBD - BST as Data Structure

Code

class Solution {
    private static class Node {
        int val;
        Node left;
        Node right;
        int count;
        int dup = 1;
        public Node(int val, int sum) {
            this.val = val;
            this.count = sum;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        int[] ans = new int[nums.length];
        Node root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            root = insert(nums[i], root, ans, i, 0);
        }

        return Arrays.stream(ans).boxed().collect(Collectors.toList());
    }

    private Node insert(int val, Node node, int[] ans, int i, int smaller) {
        if (node == null) {
            node = new Node(val, 0);
            ans[i] = smaller;
        } else if (val == node.val) {
            node.dup++;
            ans[i] = smaller + node.count;
        } else if (val < node.val) {
            node.count++;
            node.left = insert(val, node.left, ans, i, smaller);
        } else if (val > node.val) {
            node.right = insert(val, node.right, ans, i, smaller + node.count + node.dup);            
        }

        return node;
    }
}