# [leetcode] Kth Smallest Element in a BST

Kth Smallest Element in a BST

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.

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?

Hint:

1. Try to utilize the property of a BST.
2. What if you could modify the BST node’s structure?
3. The optimal runtime complexity is O(height of BST).

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Naive approach, convert BST to a sequence, find the Kth element.

O(n) in space, O(n) in time.

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
vector<TreeNode *> seq;
convert2vector(root, seq);
return seq[k - 1]->val;
}
void convert2vector(TreeNode * root, vector<TreeNode *>& seq){
if(root == nullptr){
return ;
}
convert2vector(root->left, seq);
seq.push_back(root);
convert2vector(root->right, seq);
}
};```

A better approach. Calculate the number of nodes in subtree of each node. Then use binary search.

O(h) in time for each search. h is the height of the tree. O(n) in generating the number of nodes information.

This site uses Akismet to reduce spam. Learn how your comment data is processed.