Solve for the Kth smallest element in a Binary Search Tree.

Why BST Kth Smallest: In-order traversal yields sorted order. kth smallest = kth node in in-order. Used in top-K from sorted structure, percentile queries.

Approach: (1) In-order with counter: O(h + k) time. (2) Augmented BST: each node stores subtree size—O(h) search by comparing k with left size.

Scalability: BST in-memory; for disk-backed (B-tree), similar logic. In data eng: approximate with reservoir sampling or partial sort for top-K from unsorted.

def kth_smallest(root, k):
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0: return root.val
root = root.right