Kth Smallest Element in a BST

Add Two Numbers

Diameter of Binary Tree

Return the k-th smallest value stored in a binary search tree.

Given the `root` of a binary search tree and an integer `k`, return the `k`-th smallest value among all node values in the tree (1-indexed).

**Input / output**
- Input: `root: TreeNode` (LeetCode-style level-order array, `null` marks a missing child), `k: int`
- Output: `int` — the k-th smallest node value

## Example
```json
Input: {"root":[3,1,4,null,2],"k":1}
Output: 1
```

## Constraints
- The number of nodes is between 1 and 10,000.
- `0 <= node value <= 100,000`
- `1 <= k <= number of nodes`

## Follow-up
The tree is a BST, so an in-order traversal visits nodes in sorted order — can you stop early instead of collecting every value first? If the BST is frequently modified and queried for the k-th smallest, how would you augment each node to answer in O(h) instead of O(n)?

The key pattern is: Iterative in-order traversal with an explicit stack, stopping at the k-th visit. Identify the state and invariant before coding.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

Check Edge Cases

Time: O(h + k). Space: O(h) for the stack.

All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real TreeNode structural-type support the judge added for the rest of the linked-list/tree track.