Hi,

1 Inorder-traverse

time complexity: O(n)

space complexity: O(n) + O(logn)

```
int kthSmallest(TreeNode* root, int k) {
vector<int> array;
DFS(root, array);
return array[k - 1];
}
void DFS(TreeNode* root, vector<int>& array) {
if (root) {
DFS(root->left, array);
array.push_back(root->val);
DFS(root->right, array);
}
}
```

no-brain solution. Just use inorder property to get a sorted array and index the desired entry

2.Optimization

time complexity:

average: O(nlogn)

worst: O(n^2)

```
int kthSmallest(TreeNode* root, int k) {
int count = countNode(root->left);
if (k == count + 1) return root->val;
if (k < count + 1) return kthSmallest(root->left, k);
else return kthSmallest(root->right, k - count - 1);
}
int countNode(TreeNode* root) {
if (root == nullptr) {
return 0;
}
return countNode(root->left) + countNode(root->right) + 1;
}
```

The first method requires us to traverse the entire tree, which is unnecessary. We can count how many nodes in a leftsubtree to decide the kth element may sit in left subtree or right subtree.

Also I think this solution is for the follow-up. If we modify the tree very often and call kthsmallest frequently. We can add a "count" field to each node and update it in each dynamic operation. In this way kthsmallest can be done in o(lgN);