Problem #230: Kth Smallest Element in a BST

Intuition & Strategy Breakdown

Perform controlled in-order traversal (DFS or stack). Decrement K at each node visited; return node value when K reaches 0.

Python Solution

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        curr = root
        
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            
            curr = stack.pop()
            k -= 1
            
            if k == 0:
                return curr.val
            
            curr = curr.right

Java Solution

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack 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;
    }
}