```
class Solution {
public:
int visit(TreeNode* root, int &k) {
// if there are left children...
if (root->left)
{
// ... then the k'th smallest is somewhere to the left
int res = visit(root->left,k);
// ... if we don't need to go for the next smallest
if (k == 1)
// then we are done
return res;
// otherwise we go for the next smallest
else k=k-1;
}
// if we don't need to go for the next smallest
if (k == 1)
// then we are the one
return root->val;
else
{
// otherwise, it's bigger than us, somewhere to the right.
if (root->right)
{
k = k-1;
return visit(root->right, k);
}
}
}
int kthSmallest(TreeNode* root, int k) {
return visit(root, k);
}
};
```