Kth smallest Element in a BST using c++
Kth smallest element in a BST
First Approach:
The first approach we can think of is that we traverse the tree, store the elements in a data structure (say, vectors), sort the vector, and return the (k-1)th element from the vector.
Time Complexity:
for traversing: O(n)
for sorting: O(nlogn)
Space Complexity:
for storing elements: O(n)
Second Approach:
Now we can use a property of BST. we know that in a BST, the left value is always less than the root and the right value of the root is always greater than the root. so if we now traverse the tree using the inorder method and store the elements in a vector, we will notice that the vector is already sorted. Now return the (k-1)th element from the vector.
Time Complexity:
for traversing: O(n)
Space Complexity:
for storing elements: O(n)
C++ code:
int kthSmallest(TreeNode* root, int k) {
vector<int>ans;
helper(root,ans);
return ans[k-1];
}
void helper(TreeNode* root,vector<int>&ans){
if(root==NULL)return ;
helper(root->left,ans);
ans.push_back(root->val);
helper(root->right,ans);
}Third Approach:
In this approach, we will again traverse the tree using the inorder method but this time we will not use any extra space. Instead, we will use a counter while traversing and as soon as the counter matches the kth element, we will return the element.
Time Complexity:
for Traversing: O(n)
Space Complexity:
O(1)
C++ code:
class Solution {
public:
int cnt=0,ans=0;
int kthSmallest(TreeNode* root, int k) {
if(root==NULL)return -1;
helper(root,k);
return ans;
}
void helper(TreeNode* root,int k){
if(root->left){
helper(root->left,k);
}
cnt++;
if(k==cnt){
ans=root->val;
return;
}
if(root->right){
helper(root->right,k);
}
}
};
Comments
Post a Comment