230. Kth Smallest Element in a BST
Reference: LeetCode EPI 14.3
Difficulty: Medium
Problem
Given a binary search tree, write a function
kthSmallest
to find thekth
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 
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?
Evercode: I think we can keep both the kth smallest element and (k1)th smallest element. If we insert or delete an element larger than the kth smallest element, the result remains unaffected. If something smaller than is inserted, compare it with the (k1)th smallest element. The larger one becomes the new kth smallest element and adjust (k1)th element accordingly.
Or maybe you can add another attribute like
size
to the tree nodes telling how many nodes is there in the subtree it’s rooted at?
1 

Analysis
Methods:
 Recursion
 Use a field variable to keep track of the
count
andresult
.  Use an array to keep track of the result.
 Time: $O(H + k)$
 Space: $O(H + k)$
 Use a field variable to keep track of the
 Iteration
 With the help of stack, we can convert the recursion version into iteration.
 We can use the
stack
to store everything we need.  Time: $O(H + k)$
 Space: $O(H + k)$
Code
Recursion
Note:
1  private int count; 
An alternative way is to use a list to store the element, just like the solution in EPI.
Iteration
Note:
1  public int kthSmallest(TreeNode root, int k) { 
Improvement:
 Use stack to keep track of the result.
1  public int kthSmallest(TreeNode root, int k) { 