This link suggests a concise C++ recursive solution. The original code may be hard to understand at first and I have rewritten the code below. You may need to run some examples with it to see how it works.
1 class Solution { 2 public: 3 int kthSmallest(TreeNode* root, int k) { 4 return smallest(root, k); 5 } 6 private: 7 int smallest(TreeNode* node, int& k) { 8 if (!node) return -1; 9 int val = smallest(node -> left, k); 10 if (!k) return val; 11 if (!--k) return node -> val; 12 return smallest(node -> right, k); 13 } 14 };
The same author also posts three solutions which is more space-efficient in this link. All of them reduce the O(n) space of the above code to O(k) space by using some nice data structures.
Personally I really love the soltuion using deque and I have rewritten it below.
1 class Solution { 2 public: 3 int kthSmallest(TreeNode* root, int k) { 4 TreeNode* node = root; 5 deque<TreeNode*> nodes; 6 while (true) { 7 while (node) { 8 nodes.push_front(node); 9 if (nodes.size() > k) 10 nodes.pop_back(); 11 node = node -> left; 12 } 13 node = nodes.front(); 14 nodes.pop_front(); 15 if (!--k) return node -> val; 16 node = node -> right; 17 } 18 } 19 };
