# My C++ BST based solution, 36 ms O(NlogN) average complexity, O(N) space

• The basic idea is to process num[i] one by one starting from the right side (i.e. i=n-1..0). For each num[i], insert it into a BST built with num[k] (k>i). Each BST node has a field count to save the number of nodes of the subtree rooted at such node. When doing insertion, it uses the count field to calculate res. I tried to use multset to implement such insert sorting, but multiset in C++ doesn't provide O(logN) distance operation, even it is implemented with RB tree.

``````class BSTNode{
public:
int count, val;
BSTNode *left, *right;
BSTNode(int value, int cnt) {
val = value;
count = cnt;  // count is the # of nodes of the subtree rooted at this node.
left=right=nullptr;
}
};

class Solution {
private:
int insertNum(BSTNode *root, int num, int cnt){ //cnt is the number of nodes that have less than num values from layers higher than root
++(root->count); // increase root node counter
if(root->val == num)  // if root has value of num, then the number of nodes less than num is cnt + number of nodes of its left subtree
return cnt + (root->left!=nullptr? root->left->count:0);
else if(root->val > num)
{ // goes into the left subtree, do recursiion
if(!root->left) root->left = new BSTNode(num,0);
return insertNum(root->left, num, cnt);
}
else
{ // goes into the right-subtree, update cnt as cnt + the number of nodes of its left subtree + the number of nodes with value of root->val
if(!root->right) root->right = new BSTNode(num,0);
return insertNum(root->right, num, cnt+root->count-root->right->count-1);
}
}
void deleteTree(BSTNode *root)
{//recursive destroy the tree
if(root)
{
deleteTree(root->left);
deleteTree(root->right);
delete root;
}
}

public:
vector<int> countSmaller(vector<int>& nums) {
int i, nSize = nums.size();
vector<int> res(nSize,0);
if(nSize>1)
{
BSTNode *root = new BSTNode(nums[nSize-1], 1);
for(i = nSize-2; i>=0; --i) res[i] = insertNum(root, nums[i], 0);
deleteTree(root);
}
return res;
}
};
``````

The version without dynamic BST Node new/delete

``````class BSTNode{
public:
int count, val;
BSTNode *left, *right;
BSTNode(int value=0, int cnt=0) {
val = value;
count = cnt;
left=right=nullptr;
}
};

class Solution {
private:
int insertNum(BSTNode *root, BSTNode *node, int cnt){
++(root->count);
if(root->val == node->val)
return cnt + (root->left!=nullptr? root->left->count:0);
else if(root->val > node->val)
{
if(!root->left) root->left = node;
return insertNum(root->left, node, cnt);
}
else
{
if(!root->right) root->right = node;
return insertNum(root->right, node, cnt+root->count-root->right->count-1);
}
}

public:
vector<int> countSmaller(vector<int>& nums) {
int i, nSize = nums.size();
if(nSize<=1) return vector<int>(nSize, 0);
vector<int> res(nSize,0);
BSTNode nodes[nSize];
for(nodes[nSize-1].val = nums[nSize-1], nodes[nSize-1].count =1, i = nSize-2; i>=0; --i)
{
nodes[i].val = nums[i];
res[i] = insertNum(&nodes[nSize-1], &nodes[i], 0);
}
return res;
}
};``````

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