# 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 the kth smallest element in it.

Note: You may assume $k$ is always valid, 1 ≤ k ≤ BST’s total elements.

Example:

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 (k-1)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 (k-1)th smallest element. The larger one becomes the new kth smallest element and adjust (k-1)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?

## Analysis

Methods:

1. Recursion
• Use a field variable to keep track of the count and result.
• Use an array to keep track of the result.
• Time: $O(H + k)$
• Space: $O(H + k)$
2. 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:

An alternative way is to use a list to store the element, just like the solution in EPI.

### Iteration

Note:

Improvement:

• Use stack to keep track of the result.

Comment Junhao Wang
a software engineering cat