Leetcode 230: kth smallest in binary search tree

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

 这个题目利用binary search tree inorder traversal is in ascending order的性质，对binary search tree 进行inorder的tranversal， 每次遇到root的时候k--，知道最后k=1的时候对rst 赋值并return 就可以。

class Solution {
private:
    int pre(TreeNode* root, int &k, int &rst) {
        if (root == NULL) return 0;
        pre(root->left, k, rst);
        if (k == 1) {
            rst = root->val;
        }
         k = k-1;
        pre(root->right, k, rst);
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        int rst = 0;
         pre(root, k, rst);
        return rst;
    }
};

Follow up: 更改 node 节点的结构，每个node存储左子树都多少节点，右子树有多少节点，以后只需要对binary search tree进行二分查找，相当于在node上面加了索引。