# Kth Smallest Element in a BST

#1

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?

#2

The below code uses a `Stack` to do an inorder traversal and find out the kth smallest element.

``````type Stack []*TreeNode

func (s *Stack) Push(n *TreeNode) {
*s = append(*s, n)
}

func (s *Stack) Pop() (n *TreeNode) {
x := s.Len() - 1
n = (*s)[x]
*s = (*s)[:x]
return
}

func (s *Stack) Len() int {
return len(*s)
}
func (s *Stack) Peek() *TreeNode {
x := s.Len() - 1
return (*s)[x]
}

func kthSmallest(root *TreeNode, k int) int {
if root==nil{ return -1 }
stack := Stack{}
cur := root
for cur!=nil || stack.Len()!=0 {
for cur!=nil {
stack.Push(cur)
cur = cur.Left
}

cur = stack.Pop()
k--
if k==0{return cur.Val}
cur = cur.Right
}

return -1
}
``````