# Leetcode 315 Solution

https://leetcode.com/problems/count-of-smaller-numbers-after-self

## Solution

``````struct Node
{
int m_val;
int smaller;
int count = 1;
Node* left;
Node* right;

Node(int val)
{
m_val = val;
smaller = 0;
count = 1;
left = NULL;
right = NULL;
}
};

class BST
{
Node* m_root;

Node* insert(Node* node, int val)
{
if (node == NULL)
return new Node(val);
else if (val == node->m_val)
{
node->count++;
return node;
}
else if (val < node->m_val)
{
node->smaller++;
node->left = insert(node->left, val);
return node;
}
else if (val > node->m_val)
{
node->right = insert(node->right, val);
return node;
}

return NULL;
}

int findsmaller(Node* node, int val)
{
if (node == NULL)
return 0;
else if (node->m_val == val)
return node->smaller;
else if (node->m_val > val)
return findsmaller(node->left, val);
else if (node->m_val < val)
return node->smaller + node->count + findsmaller(node->right, val);

return 0;
}

public:
BST()
{
m_root = NULL;
}

void insert(int val)
{
m_root = insert(m_root, val);
}

int findsmaller(int val)
{
return findsmaller(m_root, val);
}
};

class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
BST bst;
vector<int> res(nums.size());

for (int i = nums.size() - 1; i >= 0; i--)
{
res[i] = bst.findsmaller(nums[i]);
bst.insert(nums[i]);
}

return res;
}
};
``````