230. Kth Smallest Element in a BST LeetCode Solution
In this guide, you will get 230. Kth Smallest Element in a BST LeetCode Solution with the best time and space complexity. The solution to Kth Smallest Element in a BST problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(h)
230. Kth Smallest Element in a BST LeetCode Solution in C++
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
const int leftCount = countNodes(root->left);
if (leftCount == k - 1)
return root->val;
if (leftCount >= k)
return kthSmallest(root->left, k);
return kthSmallest(root->right, k - 1 - leftCount); // leftCount < k
}
private:
int countNodes(TreeNode* root) {
if (root == nullptr)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
}; /* code provided by PROGIEZ */
230. Kth Smallest Element in a BST LeetCode Solution in Java
class Solution {
public int kthSmallest(TreeNode root, int k) {
final int leftCount = countNodes(root.left);
if (leftCount == k - 1)
return root.val;
if (leftCount >= k)
return kthSmallest(root.left, k);
return kthSmallest(root.right, k - 1 - leftCount); // leftCount < k
}
private int countNodes(TreeNode root) {
if (root == null)
return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
} // code provided by PROGIEZ
230. Kth Smallest Element in a BST LeetCode Solution in Python
class Solution:
def kthSmallest(self, root: TreeNode | None, k: int) -> int:
def countNodes(root: TreeNode | None) -> int:
if not root:
return 0
return 1 + countNodes(root.left) + countNodes(root.right)
leftCount = countNodes(root.left)
if leftCount == k - 1:
return root.val
if leftCount >= k:
return self.kthSmallest(root.left, k)
return self.kthSmallest(root.right, k - 1 - leftCount) # leftCount < k # code by PROGIEZ
