Kth Smallest Element in a BST Leetcode Solution
Kth Smallest Element in a BST Leetcode Problem :
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 :
Input: root = [3,1,4,null,2], k = 1
Output: 1
Sliding Window maximum Leetcode Solution :
Constraints :
- The number of nodes in the tree is n.
- 1 <= k <= n <= 10^4
- 0 <= Node.val <= 10^4
Example 1:
- Input: root = [5,3,6,2,4,null,null,1], k = 3
- Output: 3
Intuition :
We can do traversal of the given tree using any traversal technique and store the node values in an array/vector. Then we can sort the array in ascending order such that the 1st smallest element comes at 0th index, 2nd smallest element at 1st index … kth samllest element at k-1th index.
Approach :
- Initialize an empty vector ‘v’.
- Do any traversal (lets say preorder) and store the node values in v.
- Sort vector v in ascending order.
- Return v[k-1].
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
void preOrderTraversal(TreeNode* root, vector< int> &v){
if(root == NULL) return;
//root, left, right
v.push_back(root->val);
preOrderTraversal(root->left, v);
preOrderTraversal(root->right, v);
}
int kthSmallest(TreeNode* root, int k) {
vector< int> v;
preOrderTraversal(root, v);
sort(v.begin(), v.end());
return v[k-1];
}
};
Java
class Solution {
int kCounter = 0;
int res = -1;
public int kthSmallest(TreeNode root, int k) {
smallest(root, k);
return res;
}
public void smallest(TreeNode node, int k) {
if (node != null) {
smallest(node.left, k);
kCounter++;
if (kCounter == k) {
res = node.val;
}
smallest(node.right, k);
}
}
}
Python
class Solution(object):
def kthSmallest(self, root, k):
values = []
self.inorder(root, values)
return values[k - 1]
def inorder(self, root, values):
if root is None:
return
self.inorder(root.left, values)
values.append(root.val)
self.inorder(root.right, values)Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment