Kth Smallest Element in a BST

Given a binary search tree, write a functionkthSmallestto find the kth smallest element in it.

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

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?

Solution #1:

The In-order traversal of BST is always ascending. We can in-order traverse the tree, and count at the same time either by using recursion or iterative method.

public int kthSmallest(TreeNode root, int k) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        k--;
        if (k == 0){
            return curr.val;
        }
        curr = curr.right;
    }
    return -1;
}

Solution #2:

Recursive.