# Sharing my 36ms C++solution

• ``````// definition of BST, specifically for this problem
struct myTreeNode
{
int val; // the value
int nLess; // the number of nodes whose value is less than the value of this node
int nSame; // the number of nodes whose value is the same as that of this node
myTreeNode* left;
myTreeNode* right;
myTreeNode(int value)
{
val = value;
nLess = 0;
nSame = 1;
left=NULL;
right=NULL;
}
};

void insert(myTreeNode* root, int value, int& nSmaller)
{
if(value<root->val)
{
root->nLess++;
if(root->left==NULL)
root->left = new myTreeNode(value);
else
insert(root->left, value, nSmaller);
}
else if(value>root->val)
{
nSmaller += (root->nSame+root->nLess);
if(root->right==NULL)
root->right = new myTreeNode(value);
else
insert(root->right, value, nSmaller);
}
else
{
root->nSame++;
nSmaller += root->nLess;
}
}

class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> result;
result.resize(n);

if(n==0)
return result;

result[n-1] = 0;
myTreeNode* root = new myTreeNode(nums[n-1]);

int nLess;
for(int i=n-2; i>=0; i--)
{
nLess = 0;
insert(root, nums[i], nLess);
result[i] = nLess;
}

return result;
}
};``````

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