class Solution {
private:
int countNodes(TreeNode* root)
{
if(!root) return 0;
return 1+countNodes(root>left)+countNodes(root>right);
}
public:
int kthSmallest(TreeNode* root, int k)
{
int lCount = countNodes(root>left);
if(lCount == k1) return root>val;
if(lCount >= k) return kthSmallest(root>left, k);
else return kthSmallest(root>right, klCount1);
}
};
Very simple binarysearch solution in C++, quite efficient


Enclosing a constant space cost yet efficient inorder traversing solution here, a
Morris
Traversing.class Solution { public: int kthSmallest(TreeNode* root, int k) { int kth = 0; while(root) { if(!root>left) { if(k == 1) kth = root>val; root = root>right; } else { TreeNode* pre = root>left; while(pre>right && pre>right!=root) pre = pre>right; if(!pre>right) { pre>right = root; root = root>left; } else { if(k == 1) kth = root>val; pre>right = NULL; root = root>right; } } } return kth; } };