Kth Smallest Element in a BST

Problem Given the root of a BST and an integer k, return the kth smallest value (1-indexed).

Input / Output

• Input: BST root, int k (1 <= k <= number of nodes).
• Output: the kth smallest key.

Constraints

• Up to 10^4 nodes; O(h + k) expected via early-terminated inorder.

Example

• BST [5,3,6,2,4,null,null,1], k = 3 → 3.

Expected approach

• Inorder traversal visits BST keys in sorted order: iterate with an explicit stack, decrementing k at each visited node; return when k hits 0 — O(h + k) time, O(h) space, no full traversal or array needed. Follow-on discussion: frequent queries with inserts/deletes → augment nodes with left-subtree counts for O(h) per query.