# 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

### 1.

``````class Solution {

// Traverse the binary search tree by non-recursive way.

public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();

TreeNode p = root;
stack.push(p);

// using loop instead of recursion
while (!stack.isEmpty() || p != null) {
// visit left until no child
if (p != null) {
stack.push(p);
p = p.left;
continue;
}

// p = null && stack not empty

// visit stack top
TreeNode t = stack.pop();
k--;
if (k == 0) {
return t.val;
}

p = t.right; // visit right
}

// never reached
return -1;
}
}
``````

### 2.

``````class Solution {

// Traverse the binary search tree by recursive way.

public int kthSmallest(TreeNode root, int k) {
Stack<Integer> track = new Stack<>();

recurse(root, k, track);

return track.pop();
}

public int recurse(TreeNode root, int k, Stack<Integer> track) {

// This should be placed at the head of function since priority of return 1
// weighs much more than return 0. return 1 means all the recursion
// searching should ceased immediately.

if (track.size() == k) {
return 1;
}

if (root == null) {
return 0;
}

int rst = recurse(root.left, k, track);
if (rst == 1) { // break down searching
return rst;
}

track.push(root.val);

rst = recurse(root.right, k, track);

return rst;
}
}
``````

## References

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