210. Kth Smallest Element in a BST
You are given root, the root node of a binary search tree, and an integer k. Return the k-th smallest value stored in the tree, counting from 1 — so k = 1 asks for the minimum.
Remember the BST invariant: at every node, everything in the left subtree is smaller than the node's value and everything in the right subtree is larger. That ordering is the whole key to this problem — a BST already knows its sorted order, you just have to read it out.
k is always valid: 1 <= k <= n, where n is the number of nodes.
Example 1:
Input: root = [3, 1, 4, null, 2], k = 1
Output: 1
Explanation: The values in sorted order are 1, 2, 3, 4; the 1st smallest is 1.
Example 2:
Input: root = [5, 3, 6, 2, 4, null, null, 1], k = 3
Output: 3
Explanation: Sorted, the values are 1, 2, 3, 4, 5, 6; the 3rd smallest is 3.
Constraints:
- 1 ≤ n ≤ 10⁴ (n is the number of nodes)
- 0 ≤ Node.val ≤ 10⁴
- All node values are distinct
- 1 ≤ k ≤ n
Hints:
What traversal order visits a BST's values from smallest to largest? Left subtree, node, right subtree — inorder.
The easy version: run a full inorder traversal into a list and return element k−1. Works, but it visits every node and stores all n values.
To stop early, make the traversal iterative: push nodes onto a stack while walking left, then pop. Each pop is the next value in sorted order — the k-th pop is your answer, and you never touch the rest of the tree.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 1, 4, null, 2], k = 1
Expected output: 1