Intermediate Level
Implement the kthSmallestInBst method that returns the kth smallest value from a binary search tree.
The input contains a binary search tree, its size, and an integer k.
Your task is to return the kth smallest value in the BST. In a binary search tree, an inorder traversal visits the values in ascending order.
For example, if k is 1, return the smallest value in the tree.
Example 1
Input
tree (int[]) =
[3,1,4,0,2]size (int) =
5k (int) =
1Returns (int)
1Example 2
Input
tree (int[]) =
[5,3,6,2,4,0,0,1]size (int) =
8k (int) =
3Returns (int)
3Example 3
Input
tree (int[]) =
[1]size (int) =
1k (int) =
1Returns (int)
1Use inorder traversal because it gives BST values from smallest to largest.
Visit the left subtree first, then the current node, then the right subtree. Count how many valid nodes have been visited. When the count becomes k, the current value is the answer.
This avoids sorting because the BST structure already provides sorted order through inorder traversal.
Pseudocode:
function kthSmallestInBst(tree, size, k):
count = 0
answer = -1
inorder(0)
return answer
function inorder(index):
if index >= size or tree[index] is missing or answer != -1:
return
inorder(2 * index + 1)
count++
if count == k:
answer = tree[index]
return
inorder(2 * index + 2)Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run