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 <= 1040 <= 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);
}
Input
root = [3,1,4,null,2], k = 1
Output
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;
}
}
Input
root = [3,1,4,null,2], k = 1
Output
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
}
Input
root = [5,3,6,2,4,null,null,1], k = 3
Output
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
Input
root = [5,3,6,2,4,null,null,1], k = 3
Output
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);
values.Add(node.val);
InOrder(node.right, k, values);
}
}
}
Input
root = [3,1,4,null,2], k = 1
Output
1