# 9ms Java BST solution with explanations

• When doing insertions in BST, every move (exploring left or right) implies that half of the sub-tree is smaller/greater than the node you're inserting.

So, this solution exploits this by summing the sizes of left sub-trees one insertion passes.

This solution deals with equality by counting the occurrences of every node in the BST. In conclusion, counts[i] = sum(sizes of left sub-trees passed + occurrences of the roots of the corresponding sub-trees).

``````public class Solution {
public List<Integer> countSmaller(int[] nums) {
int len;
List<Integer> res = new ArrayList<>();
if (nums == null || (len = nums.length) == 0) {
return res;
}
Integer[] tmp = new Integer[len];
BST bst = new BST();
for (int i = len - 1; i >= 0; i--) {
tmp[i] = bst.insert(nums[i]);
}
return res;
}

private static class BST {
private Node root;

private int insert(int val) {
int sCnt = 0;
if (root == null) {
root = new Node(val);
return sCnt;
}
Node cur = root;
while (true) {
if (cur.val < val) {
sCnt += cur.lCnt + cur.selfCnt;
if (cur.right == null) {
cur.right = new Node(val);
return sCnt;
}
else {
cur = cur.right;
}
}
else if (cur.val > val) {
cur.lCnt++;
if (cur.left == null) {
cur.left = new Node(val);
return sCnt;
}
else {
cur = cur.left;
}
}
// equal
else {
sCnt += cur.lCnt;
cur.selfCnt++;
return sCnt;
}
}
}
}

private static class Node {
private int val;
private Node left;
private Node right;
// size for left sub-tree
private int lCnt;
// cnt for self occurances
private int selfCnt;

private Node(int val) {
this.val = val;
selfCnt = 1;
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.