# Quite standard in-order traversal recursive C++ solution

• Just do in-order traversal recursively, use k to track how many nodes it still needs to visit. Everytime, you visit a node, decrease k by one, if k reaches 0, return the current node value. worst case O(N) space, O(N) time.
If there is a space limit, then use Morris traversal method to achieve O(1) space.

For the follow-up question, for each node, include two new fields to save the number of nodes of its left subtree and right subtree, so we can do binary search.

``````    class Solution {
private:
bool inOrder(TreeNode* root, int &k, int &res)
{
if(!root) return false;
// if we found the k-th entry in the left subtree, then return
if(inOrder(root->left, k, res)) return true;
// otherwise, visit the current node, if it is the k-th node, just return with true
if(!--k)
{
res = root->val;
return true;
}
//otherwise, traverse the right subtree
return inOrder(root->right, k, res);
}
public:
int kthSmallest(TreeNode* root, int k) {
int res;
inOrder(root, k, res);
return res;
}
};``````

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