# Share my AC BST solution

• Store extra info leftSize and selfSize in the treeNode.
And add the nodes to the tree using the reverse order of the array
So, all the numbers after it self will be store in the tree before it.
Remember using the selfSize to deal with duplicates.

``````public class Node {
Node left;
Node right;
int val;
int leftSize;
int selfSize;
public Node(int val) {
this.val = val;
selfSize = 1;
}
}
public List<Integer> countSmaller(int[] nums) {
List<Integer> list = new LinkedList<>();
int n = nums.length;
if (n == 0) {
return list;
}
Node root = new Node(nums[n - 1]);
for (int i = n - 2; i >= 0; i--) {
list.add(0, addToTree(root, nums[i])); // add to the front of list
}
return list;
}

private int addToTree(Node root, int val) {
int num = 0; // store the count less than it
Node current = root;
while (true) {
if (current.val < val) {
num += current.leftSize + current.selfSize;
if (current.right == null) {
current.right = new Node(val);
break;
}
current = current.right;
} else if (current.val > val) {
current.leftSize++; // remember to update the path nodes info
if (current.left == null) {
current.left = new Node(val);
break;
}
current = current.left;
} else {
current.selfSize++; // duplicates
num += current.leftSize;
break;
}
}
return num;
}``````

• In the worst case, the tree needs to be balanced to avoid quadratic runtime, though it is not covered by the test cases.

• Yes, so AVL is a better choice.

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