# 230. Kth Smallest Element in a BST (Medium)

https://leetcode.com/problems/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.

Example 1:

```Input: root = [3,1,4,null,2], k = 1
3
/ \
1   4
\
2
Output: 1```

Example 2:

```Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3   6
/ \
2   4
/
1
Output: 3
```

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?

## Solutions

https://www.programcreek.com/2014/07/leetcode-kth-smallest-element-in-a-bst-java/

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<TreeNode>();

TreeNode p = root;
int result = 0;

while(!stack.isEmpty() || p!=null){
if(p!=null){
stack.push(p);
p = p.left;
}else{
TreeNode t = stack.pop();
k--;
if(k==0)
result = t.val;
p = t.right;
}
}

return result;
}
}
``````