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

Follow up:
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
}