Tree Binary Tree Binary Search Tree Breadth First Search Depth First Search
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) = 5
k (int) = 1
Return:
(int) 1
Example 2
Input:
tree (int[]) = [5,3,6,2,4,0,0,1]
size (int) = 8
k (int) = 3
Return:
(int) 3
Example 3
Input:
tree (int[]) = [1]
size (int) = 1
k (int) = 1
Return:
(int) 1

Use 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)
Run your code to see the result.