Kth Smallest Element in a BST — Step-by-Step Visualization

Algorithm Pattern

In-Order Traversal (LNR)

Key Idea

A key property of a Binary Search Tree (BST) is that an in-order traversal (Left, then Node, then Right) visits nodes in strictly increasing order. To find the Kth smallest element, we perform an in-order traversal and return the Kth node we visit.

Step-by-Step Approach

1. Initialize a counter `n = 0`.
2. Perform an in-order traversal (recursive or iterative with a stack).
3. Whenever you 'visit' a node (after finishing its left subtree):
4. Increment `n`.
5. If `n == k`, total success! This is your answer.
6. Continue traversal until found.

Common Gotchas

• In-order traversal is the only traversal that yields sorted order for a BST.
• Early exit is important for efficiency once the Kth element is reached.