Question
Kth smallest element in BST
Given the
root of a binary search tree (BST) and an integer k, return the kth smallest value (1-indexed) among all node values in the tree.Input
User Task
Since this is a functional problem, you do not need to take any input. Your task is to complete the function kthSmallest(), which takes the following parameters as input:
KaTeX can only parse string typed expression — the root node of the Binary Search Tree.
KaTeX can only parse string typed expression — the index (1-based) of the smallest element to find.
Custom Input
The first line contains an integer
Each test case contains:An integer
A line with
An integer
The driver code will build the BST from the given level-order array (using
Since this is a functional problem, you do not need to take any input. Your task is to complete the function kthSmallest(), which takes the following parameters as input:
KaTeX can only parse string typed expression — the root node of the Binary Search Tree.
KaTeX can only parse string typed expression — the index (1-based) of the smallest element to find.
Custom Input
The first line contains an integer
t — the number of test cases.Each test case contains:
n — the number of entries in the level-order representation (including -1 placeholders).n space-separated integers describing the tree in level-order. Each integer is either a valid node value or -1 (for a missing child).k.-1 for absent children).Output
For each test case, return a single integer — the
kth smallest value in the BST.
Example
Input
Output
Explanation
In the given BST, 1st smallest element is 1.
In the given BST, 3rd smallest element is 3.
2
5
3 1 4 -1 2
1
8
5 3 6 2 4 -1 -1 1
3
Output
1
3
Explanation
In the given BST, 1st smallest element is 1.
In the given BST, 3rd smallest element is 3.