Kth Smallest Element in a BST

Kth Smallest Element in a BST

1. What is this problem about?

The Kth Smallest Element in a BST interview question asks you to find the $k^{th}$ node in sorted order within a Binary Search Tree. Because of the BST property (Left < Root < Right), the sorted order of elements is exactly the order in which they are visited during an in-order traversal.

2. Why is this asked in interviews?

Companies like Amazon, Microsoft, and Google use the Kth Smallest coding problem to test a candidate's knowledge of Tree Traversals. It evaluates whether you understand that an in-order traversal of a BST is equivalent to visiting elements in ascending order. It also provides an opportunity to discuss optimization: can you find the element in $O(H)$ time if the tree is modified frequently?

3. Algorithmic pattern used

This problem follows the In-order Traversal (DFS) pattern.

1. Iterative In-order: Use a stack to simulate recursion.
2. Count: Keep track of how many nodes you have "processed" (popped from the stack).
3. Termination: When the count reaches $k$, the current node is the $k^{th}$ smallest.
4. Optimization: If you can store the size of each subtree in the nodes, you can find the $k^{th}$ element in $O( ext{height})$ by comparing $k$ with the size of the left subtree.

4. Example explanation

BST: Root 3, Left 1, Right 4. 1 has Right child 2. $k = 3$.

1. Stack: [3, 1].
2. Pop 1. Count = 1. Node 1 has right child 2. Push 2. Stack: [3, 2].
3. Pop 2. Count = 2.
4. Pop 3. Count = 3. Found! Result: 3.

5. Common mistakes candidates make

• Full traversal: Doing a complete DFS to collect all elements into a list ($O(N)$ space) instead of stopping as soon as $k$ is reached ($O(H)$ space).
• Index errors: Confusing 0-based and 1-based indexing for $k$.
• BST property: Failing to use the BST property and treating it like a general binary tree.

6. Interview preparation tip

Always remember the golden rule of BSTs: In-order = Sorted. If a problem mentions "rank," "smallest," or "largest" in a BST, your first thought should be an in-order traversal. This is a core Binary Search Tree interview pattern.