class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
if (root == NULL)
return INT_MAX;
stack<TreeNode*> s;
TreeNode *temp = root;
while (!s.empty()  temp != NULL)
{
while (temp != NULL)
{
s.push(temp);
temp = temp>left;
}
temp = s.top();
k;
if (k == 0)
return temp>val;
s.pop();
temp = temp>right;
}
return INT_MIN;
}
};
Share my C++ solution,easy to understand And offer pseudocode of O(height of BST)


O(height of BST) Solution:
if we could modify the BST node's structure,like following: struct TreeNode { int val; int leftTotal;//the total nodes in the left subtree TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; Then we can get the optimal runtime complexity : O(height of BST). Of course we should compute 'leftTotal' when we establish the BST or Traversing the BST beforehand. The pseudocode: 1. if k == (currentNode>leftTotal + 1), return; 2. else if k > (currentNode>leftTotal + 1), let k = k  (currentNode>leftTotal + 1) and currentNode = currentNode>right; 3. else currentNode = currentNode>left;

When update the BST, we also need the 'rightTotal'. Or wehave to traverse the total BST each time after modifing the BST. Using 'rightTotal', the time complexity is O(H).
Inserting or Deleting nodes, we have to update all nodes in the path of from the root to a leaf, which has been inserted or deleted. Deleting nonleaf nodes can transform to deleting leaf nodes.
If modifing the BST is frequently, maintain these nodes will cost lots of time. So, this solution suites to less modifing situation.