As we know, in order traverse on a BST will generate sorted list.

```
public int kthSmallest(TreeNode root, int k) {
int count = countNodes(root.left);
if (k <= count) {
return kthSmallest(root.left, k);
} else if (k > count + 1) {
return kthSmallest(root.right, k-1-count); // 1 is counted as current node
}
return root.val;
}
public int countNodes(TreeNode n) {
if (n == null) return 0;
return 1 + countNodes(n.left) + countNodes(n.right);
}
```

As for optimization, we can just keep a the result list. If next time the tree does not change, we just use the list stored, otherwise if there is a change by the next time we call kthSmallest, we update the list in the kthSmallest and store the new list. I think this is called lazy update.