# LeetCode: 230. Kth Smallest Element in a BST

**The Problem**

Given the `root`

of a binary search tree, and an integer `k`

, return *the*`k`

^{th}*smallest value (1-indexed) of all the values of the nodes in the tree*.

**Example**

```
Input: [3,1,4,null,2], k = 1
Output: 1
```

**Constraints:**

- The number of nodes in the tree is
`n`

. `1 <= k <= n <= 10`

^{4}`0 <= Node.val <= 10`

^{4}

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
int kthSmallest(TreeNode* root, int k) {
int ans = 0;
kthSmallestHelper(root, k, ans);
return ans;
}
void kthSmallestHelper(TreeNode *&root, int &k, int &ans) {
if (root == NULL) return;
kthSmallestHelper(root->left, k, ans);
--k;
if(k == 0) {
ans = root->val;
return;
}
kthSmallestHelper(root->right, k, ans);
}
```

ðŸ§

Github with all the solution including test cases.

Here's how the code works step by step:

- The
`kthSmallest`

function is the entry point. It initializes a variable`ans`

to store the result, which will be the kth smallest element. It then calls the`kthSmallestHelper`

function with the root node,`k`

, and`ans`

as arguments. - The
`kthSmallestHelper`

function is a recursive helper function that navigates the BST to find the kth smallest element. It takes three parameters: a reference to the current root node (`TreeNode *&root`

), a reference to the remaining number of elements to find (`int &k`

), and a reference to store the result (`int &ans`

). - The function first checks if the current node
`root`

is NULL. If it is, it means we have reached a leaf node or a null child, so there's nothing to do, and the function returns. - The function then recursively calls itself on the left subtree (
`root->left`

). This is done to traverse the BST in an in-order fashion, which ensures that we visit the elements in ascending order. - After the left subtree has been processed, the function decrements
`k`

by 1. This represents the number of remaining elements to find. - Next, the function checks if
`k`

has reached 0. If`k`

is equal to 0, it means we have found the kth smallest element. In this case, it sets`ans`

to the value of the current node's value (`root->val`

) and returns. This termination condition ensures that we stop the traversal as soon as we find the kth smallest element. - If
`k`

is still greater than 0 after decrementing, it means we haven't found the kth smallest element yet, so the function continues the traversal by recursively calling itself on the right subtree (`root->right`

).

The in-order traversal of the BST and the decrementing of `k`

ensure that we find the kth smallest element in the BST efficiently. Once the kth smallest element is found, it is stored in the `ans`

variable, which is returned by the `kthSmallest`

function as the final result.