A large-scale platform maintains sorted hierarchical data such as:
- ranked user scores
- ordered transactions
- priority-based records
To efficiently manage and query this data, the system uses a Binary Search Tree (BST), where:
- Left subtree contains smaller values
- Right subtree contains larger values
The platform frequently needs to retrieve the kth smallest value in the dataset — for example:
- finding the kth lowest price
- retrieving kth ranked user
- selecting kth priority task
Because the data is dynamic and structured as a BST, the system must efficiently compute this value using tree properties.
This is a classic coding interview problem frequently asked in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest element in the tree.
Input Format
root: root node of a BSTk: integer (1-based index)
Each node:
TreeNode {
int val;
TreeNode left;
TreeNode right;
}
Output Format
- Return an integer representing the kth smallest value
Examples
Example 1:
Input: root = [3,1,4,null,2], k = 1
Output: 1
Explanation: Inorder traversal → [1, 2, 3, 4] → 1st smallest = 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: Inorder → [1,2,3,4,5,6] → 3rd smallest = 3