Leetcode: Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].

 1 public class Solution {
 2     public List<Integer> countSmaller(int[] nums) {
 3         List<Integer> res = new ArrayList<Integer>();
 4         if (nums == null || nums.length == 0) return res;
 5         TreeNode root = new TreeNode(nums[nums.length-1]);
 6         res.add(0);
 7         for (int i=nums.length-2; i>=0; i--) {
 8             res.add(insert(root, nums[i]));
 9         }
10         Collections.reverse(res);
11         return res;
12     }
13     
14     public int insert(TreeNode root, int num) {
15         int thisCount = 0;
16         while (true) {
17             if (root.val >= num) {
18                 root.count++;
19                 if (root.left == null) {
20                     root.left = new TreeNode(num);
21                     break;
22                 }
23                 else {
24                     root = root.left;
25                 }
26             }
27             else {
28                 thisCount += root.count;
29                 if (root.right == null) {
30                     root.right = new TreeNode(num);
31                     break;
32                 }
33                 else {
34                     root = root.right;
35                 }
36             }
37         }
38         return thisCount;
39     }
40     
41     public class TreeNode {
42         int val;
43         TreeNode left;
44         TreeNode right;
45         int count;
46         public TreeNode(int value) {
47             this.val = value;
48             this.count = 1;
49         }
50     }
51 }