binary-tree
binary-search-tree
depth-first-search
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,nullmarks a missing child),k: int - Output:
int— the k-th smallest node value
Constraints
- The number of nodes is between 1 and 10,000.
0 <= node value <= 100,0001 <= 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)?
Examples
Example 1
Input: root = [3,1,4,null,2], k = 1
Output: 1
Example 2
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Example 3 (single node)
Input: root = [1], k = 1
Output: 1
🔒 6 hidden
Running will execute all 9 cases, including 6 hidden ones.