## Algorithm

Problem Name: 230. Kth Smallest Element in a BST

Given the `root` of a binary search tree, and an integer `k`, return the `kth` smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes in the tree is `n`.
• `1 <= k <= n <= 104`
• `0 <= Node.val <= 104`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int count(struct TreeNode *node) {
if (!node) return 0;
return count(node->left) + count(node->right) + 1;
}
int kthSmallest(struct TreeNode* root, int k) {
struct TreeNode *node = root;
int n;
n = count(node->left);
if (n == k - 1) {
return node->val;
} else
if (n >= k) {
return kthSmallest(node->left, k);
}
return kthSmallest(node->right, k - n - 1);
}
``````
Copy The Code &

Input

cmd
root = [3,1,4,null,2], k = 1

Output

cmd
1

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int kthSmallest(TreeNode root, int k) {
Integer result = null;
Stack < TreeNode> stack = new Stack<>();
while (root != null) {
stack.push(root);
root = root.left;
}
while (k > 1 && !stack.isEmpty()) {
TreeNode removed = stack.pop();
TreeNode rightNode = removed.right;
while (rightNode != null) {
stack.push(rightNode);
rightNode = rightNode.left;
}
k--;
}
return stack.peek().val;
}
}
``````
Copy The Code &

Input

cmd
root = [3,1,4,null,2], k = 1

Output

cmd
1

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const kthSmallest = function (root, k) {
const st = []
while (root !== null) {
st.push(root)
root = root.left
}
while (k !== 0) {
const n = st.pop()
k--
if (k === 0) return n.val
let right = n.right
while (right !== null) {
st.push(right)
right = right.left
}
}
return -1
}
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,null,1], k = 3

Output

cmd
3

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def __init__(self):
self.k, self.res = 0, None
def kthSmallest(self, root, k):
if self.k < k and root.left: self.kthSmallest(root.left, k)
self.k += 1
if self.k == k: self.res = root.val
if self.k < k and root.right: self.kthSmallest(root.right, k)
return self.res
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,null,1], k = 3

Output

cmd
3

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0230_KthSmallestElementInABST
{
public int KthSmallest(TreeNode root, int k)
{
var list = new List < int>();
InOrder(root, k, list);
return list[k - 1];
}

public void InOrder(TreeNode node, int k, IList < int> values)
{
if (values.Count >= k) return;
if (node == null) return;

InOrder(node.left, k, values);
InOrder(node.right, k, values);
}
}
}
``````
Copy The Code &

Input

cmd
root = [3,1,4,null,2], k = 1

Output

cmd
1