Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest value (1-indexed) among all the values of the nodes in the tree.
Examples
Input: root = [3,1,4,null,2], k = 1
Output: 1
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Approach
- Since it’s a BST, an in-order traversal gives values in ascending order.
- Perform in-order traversal and decrement
kuntil it reaches 0. - Return the node’s value where
k == 0.
Time & Space Complexity
- Time Complexity: O(n) in the worst case (if k is near n)
- Space Complexity: O(n) due to recursion stack
var kthSmallest = function(root, k) {
let ans = null;
let count = k;
let traversal = (curr) => {
if (ans !== null) return;
if (curr.left) traversal(curr.left);
count--;
if (count === 0) {
ans = curr.val;
return;
}
if (curr.right) traversal(curr.right);
}
traversal(root);
return ans;
};
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int count = k;
int ans = -1;
inorder(root, count, ans);
return ans;
}
private:
void inorder(TreeNode* node, int &count, int &ans) {
if (!node || count == 0) return;
inorder(node->left, count, ans);
count--;
if (count == 0) {
ans = node->val;
return;
}
inorder(node->right, count, ans);
}
};
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
void inorder(struct TreeNode* root, int* k, int* result) {
if (!root || *k == 0) return;
inorder(root->left, k, result);
(*k)--;
if (*k == 0) {
*result = root->val;
return;
}
inorder(root->right, k, result);
}
int kthSmallest(struct TreeNode* root, int k) {
int result = -1;
inorder(root, &k, &result);
return result;
}
class Solution {
private int count;
private int result;
public int kthSmallest(TreeNode root, int k) {
count = k;
inorder(root);
return result;
}
private void inorder(TreeNode node) {
if (node == null || count == 0) return;
inorder(node.left);
count--;
if (count == 0) {
result = node.val;
return;
}
inorder(node.right);
}
}
class Solution:
def kthSmallest(self, root, k):
self.k = k
self.result = None
def inorder(node):
if not node or self.result is not None:
return
inorder(node.left)
self.k -= 1
if self.k == 0:
self.result = node.val
return
inorder(node.right)
inorder(root)
return self.result
public class Solution {
private int count;
private int result;
public int KthSmallest(TreeNode root, int k) {
count = k;
InOrder(root);
return result;
}
private void InOrder(TreeNode node) {
if (node == null || count == 0) return;
InOrder(node.left);
count--;
if (count == 0) {
result = node.val;
return;
}
InOrder(node.right);
}
}
