# C++ BST Solution

• ``````struct TNode {
TNode(int val) : val(val), cnt(0), left(NULL), right(NULL) {}

int val;
int cnt;
TNode* left;
TNode* right;
};

class Solution {
public:
int insertNode(TNode* curNode, int val, int t) {
if(curNode->val < val) {
if(curNode->right)
return insertNode(curNode->right, val, curNode->cnt + t + 1);

TNode* newNode = new TNode(val);
curNode->right = newNode;
t += curNode->cnt + 1;
}
else if(val <= curNode->val) {
curNode->cnt++;
if(curNode->left)
return insertNode(curNode->left, val, t);

TNode* newNode = new TNode(val);
curNode->left = newNode;
}

return t;
}

vector<int> countSmaller(vector<int>& nums) {
if(nums.size() == 0) return vector<int>();

vector<int> result = { 0 };
TNode *root = new TNode(nums.back());
for(int i = nums.size() - 2; i >= 0; i--)
result.push_back(insertNode(root, nums[i], 0));

reverse(result.begin(), result.end());
return result;
}
};``````

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