Your second method is basically inorder traversal with slight modification. This modification is helpful in reducing time complexity. Nice approach bro👌👌👌
It could be done in O(N) TC and O(1) SC (iteratively) using Morris Traversal. Please try to cover that approach also, because other places it is very tough.
Hi Thanks a lot for your contentious effort. Really your videos make concept clean and more understandable. Request you to upload videos on LinkedList and Other Importand data structure and also video about FANG(Facebook Amazon Google Netflix) Interview preparation.Thanks
Where i can learn to compute time complexity of a problem? Not easy problems time complexity but some hard problems like seive or any other which requires some heavy computations
I think just finding the mathematical formulation should be enough for time analysis. Solving a hard problem is difficult. Not calculating it's time 😅 Can you give some examples where you find difficulty. Most hard problems have some pattern like (DP+ BitMasking) is generally pow(2,N) for mask and multiplied by N or N^2 for iterations etc.
There is some diff between how parameters are processed by python and c++ which I am not aware, though pytthon by default passes by reference. I had to use class variable to solve above 2nd method. self.k = k return self.inorder(root) def inorder(self, root): if not root: return 0 ele1 = self.inorder(root.left) if ele1: return ele1 self.k -=1 if self.k == 0: return root.val ele2 = self.inorder(root.right) return ele2
@@techdose4u You're right. I took a look at the fastest submission, and it was doing almost the exact same thing. Then I changed: if(node === null) to if(!node) and the time went from 93ms to 68ms.
I had solved it using the same approach in java but i nvr forget to watch your video because i love the way you explain. // Java Code class Temp{ int k = 0; Temp(){ k = 0; } } class Solution { public int kthSmallest(TreeNode root, int k, Temp t) { if(root == null) return -1; int left = kthSmallest(root.left, k, t); t.k++;
Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine? so there is a follow up ques as well.. how will we approach that ?
Actually this I already explained in method 3. If you can save no of left subtree nodes then by inserting a node or deleting it, you will have to update all parents of the node added. Simple.
Nice explanation sir...but i think time complexity for second method should be o(k) not o(n) as as we are not traversing every node of the tree....please reply sir
public int kthSmallest(TreeNode root, int k) { if(root == null) { return 0; } return helper(root, k); } public int helper(TreeNode root, int k) { if(root == null) { return 0; } int left = helper(root.left, k); if(left != 0) { return left; } k = k - 1; if(k == 0) { return root.val; } int right = helper(root.right, k); return right; } why this is not working??
Bro your videos are very nice, and you explain in such a way that it is easy to understand the underlying concept. Thanks for the great work dude!! Keep on creating such work♥️.
Your second method is basically inorder traversal with slight modification.
This modification is helpful in reducing time complexity.
Nice approach bro👌👌👌
Yes 👍
it imporves space complexity as well........in first method o(n) space was req. in 2nd o(1)
It could be done in O(N) TC and O(1) SC (iteratively) using Morris Traversal. Please try to cover that approach also, because other places it is very tough.
Hi Thanks a lot for your contentious effort. Really your videos make concept clean and more understandable.
Request you to upload videos on LinkedList and Other Importand data structure and also video about FANG(Facebook Amazon Google Netflix) Interview preparation.Thanks
Yea will continue after this month.
Thank you sir for your help. Vey well taught.
I like your work, I have referred to your video a lot. Keep it up
Thanks :)
I used these approaches:
class Solution {
public:
vector v;
int val;
void inOrder(TreeNode* root){
if(!root || v.size() == val) return;
inOrder(root->left);
v.push_back(root->val);
inOrder(root->right);
}
int kthSmallest(TreeNode* root, int k) {
val = k;
inOrder(root);
return v[k-1];
}
};
and another after reading leetcode article using stack:
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack s;
while(true){
while(root){
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if (--k == 0) return root->val;
root = root->right;
}
}
};
Multiple approaches!! Nice :)
i also used 1st apporach but i think it is not optimized...
@@amruthap6334 yes ,since it uses extra spaces for vector
Nice explanation...
can u tell me which software you are using for teaching?
why return right is done ? if k=1 , then what will be return by right ? if element is found in left subtree, then what ? then also return right ?
Your explanations are always great:)
Thanks
# python code
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def helper(node,B):
if node is None:
return None
nleft=helper(node.left,B)
if nleft:
return nleft
B[0]-=1
if B[0]==0:
return node.val
nright=helper(node.right,B)
if nright:
return nright
class Solution:
def kthsmallest(self, root,k):
visited=[k]
return helper(root,visited)
Bro please. Explain perfect square GOOGLE KICKSTART question
I think you meant perfect subarray correct??
@@techdose4u yes bro
When will u expalin
Planning this weekend only....
@@techdose4u thanks bro for making such efforts
Could you also make videos involving concepts like trees, graphs..etc. and not only questions. It would be great if you do this
Yes I will. But let this contest end 😅
I think he will be able to make videos after this May Challenge only 😀
Yes correct
No I would actually prefer this as solutions of such high quality are rare on RUclips.
It gives wrong ans (0) for [5,3,6,2,4,null,null,1] 3. input but correct ans is 3 why??
Where i can learn to compute time complexity of a problem? Not easy problems time complexity but some hard problems like seive or any other which requires some heavy computations
I think just finding the mathematical formulation should be enough for time analysis. Solving a hard problem is difficult. Not calculating it's time 😅 Can you give some examples where you find difficulty. Most hard problems have some pattern like (DP+ BitMasking) is generally pow(2,N) for mask and multiplied by N or N^2 for iterations etc.
There is some diff between how parameters are processed by python and c++ which I am not aware, though pytthon by default passes by reference.
I had to use class variable to solve above 2nd method.
self.k = k
return self.inorder(root)
def inorder(self, root):
if not root:
return 0
ele1 = self.inorder(root.left)
if ele1:
return ele1
self.k -=1
if self.k == 0:
return root.val
ele2 = self.inorder(root.right)
return ele2
👍
Is it a glitch or what ? Many videos of this playlist has only this video
Why do you say space complexity is O(n) for 2nd approach ? I think we are not using any extra space so it should be O(1)
the space complexity is because of the recursion stack. in the worst case it can be O(n) i.e in the case of skewed tree
very nicely explained
Thanks :)
I implemented approach 2 and got 19.54% on the time. I was hoping you had something better.
I got 98.23% for my code. If you can see the submissions then everyone have used either stack or recursion.
@@techdose4u You're right. I took a look at the fastest submission, and it was doing almost the exact same thing. Then I changed:
if(node === null) to if(!node)
and the time went from 93ms to 68ms.
I had solved it using the same approach in java but i nvr forget to watch your video because i love the way you explain.
// Java Code
class Temp{
int k = 0;
Temp(){
k = 0;
}
}
class Solution {
public int kthSmallest(TreeNode root, int k, Temp t) {
if(root == null)
return -1;
int left = kthSmallest(root.left, k, t);
t.k++;
if(left != -1)
return left;
if(t.k == k)
return root.val;
return kthSmallest(root.right, k, t);
}
public int kthSmallest(TreeNode root, int k) {
return kthSmallest(root, k, new Temp());
}
}
Thanks :)
Hi, do you have an idea about the follow up quesiton of 230? the official answer is like sht
I have used In order:github.com/RajeshAatrayan/InterviewPreparation/blob/master/src/Trees/KthSmallestElementinaBST.java
👍
what will be the complexity of 1st approach?
O(N)
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
so there is a follow up ques as well.. how will we approach that ?
My idea here is to add the number of left and right nodes to to each node. that way you know if you should search left or right
Actually this I already explained in method 3. If you can save no of left subtree nodes then by inserting a node or deleting it, you will have to update all parents of the node added. Simple.
@@techdose4u but we cant use that approach.. thanx ...
Yes we cannot because we are not allowed to modify nodes.
Nice explanation sir...but i think time complexity for second method should be o(k) not o(n) as as we are not traversing every node of the tree....please reply sir
O(n) is for worst case for example if the element we are looking for is the last element then we have to traverse the whole tree.
Your explanations are really good!
Thanks 😊
Sir what is orderstastics in bst...for finding kth smallest or kth largest ..or n elements after k th smallest element.Please add to your Queue sir.
can u please tell me what does this means
int left = check(root->left, k);
And also how to take these things while solving recursion.
public int kthSmallest(TreeNode root, int k)
{
if(root == null)
{
return 0;
}
return helper(root, k);
}
public int helper(TreeNode root, int k)
{
if(root == null)
{
return 0;
}
int left = helper(root.left, k);
if(left != 0)
{
return left;
}
k = k - 1;
if(k == 0)
{
return root.val;
}
int right = helper(root.right, k);
return right;
}
why this is not working??
There are many repeated videos in this playlist.
I don't really know about this bug but today I corrected may challenge playlist. I will check again.
Bro your videos are very nice, and you explain in such a way that it is easy to understand the underlying concept.
Thanks for the great work dude!!
Keep on creating such work♥️.
Thanks :)
Nice code 🔥🔥🔥
Why you are doing (k-1) == 0
indexing starts from 0
in second method how 6 is smallest element
It's not the smallest element it's the 5th smallest element in bst
Awsm i understood the concept
Nice :)
Well done 👌
Thanks :)
Where do u work