Select a One-Based Inorder Rank in a Search Tree
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the value at one-based rank k in a binary search tree's inorder sequence. root is the original TreeNode pointer with val, left and right fields; a displayed tree is only an illustration.
```cpp
int kthSmallest(TreeNode* root, int k);
```
### Examples
```text
root = [6,3,9,1,4], k = 4 -> 6
root = [0], k = 1 -> 0
```
### Constraints
- The tree has n nodes, with 1 <= k <= n <= 10000.
- Node values lie in [0,10000].
### Optional follow-up
If insertions and deletions are frequent and rank queries are repeated, how would you optimize?
Overview: Select a One-Based Inorder Rank in a Search Tree. Return the value at one-based rank k in a binary search tree's inorder sequence. root is the original TreeNode pointer with val, left and right fields; a displa