In largest, we can traverse right node left and then apply the same logic.. You can also contribute an article for this video: takeuforward.org/contribute/help-us-grow-takeuforward/ Will be continuing with this setup, as youtube tends to push videos with human appearance!!
@takeUforward Thank you so much anna🤩🤩🤩🤩🤩🤩..... keep doing more and more videos anna.... For finding smallest using #InorderMorrisTraversal (left, root, right) :- code🔥🔥🔥🔥🔥🔥:- int kthSmallest(TreeNode* root, int k) { TreeNode* cur = root; int ans; int count =0; while(cur != nullptr){
} else{ TreeNode* prev = cur -> left; while(prev -> right != nullptr && prev -> right != cur){ prev = prev -> right;
} if(prev -> right== nullptr){ prev -> right = cur; cur = cur -> left; } else{ count += 1; prev -> right = nullptr; if(count == k){ ans =cur -> val; }
cur = cur -> right;
} } } return ans; } for finding largest using #reversalInorderMorrisTraversal (right root left) :- code🔥🔥🔥🔥🔥🔥:- int kthLargest(Node* root, int k) { Node* cur = root; int ans; int count =0; while(cur != nullptr){
Just a small observation In the kth largest problem if we take reverse inorder than the elements are sorted in descending fashion, so we can directly get kth largest element
we can also do this by doing inorder traversal (this will make the vector in sorted format) and then finding the kth smallest no. in it. time complexity will be O(n) + O(n)
For the kth largest question, we don't even need to make the adjustment as (n-k)th smallest element. We can simply reverse the order of traversal as - Right - Root - Left
Bhaiya it may be n+1-k th element..as for if we have 4 nodes then 2nd element from last will be 4+1-2 th i.e 3rd node.thats why I am saying about this confusion
I think Kth largest element can be done in single traversal. By using reverse inorder traversal i.e.(Right-Node-Left) .Then we can easily figure out kth largest element in single traversal. Just require few modification in code: int kthLargest(TreeNode* root, int k) { stack st; TreeNode* node = root; int cnt = 0; while(true) { if(node != NULL) { st.push(node); node = node->right; } else {
If we do simple recursive inorder traversal then time complexity should be O(k) because we don't need to go further after getting kth smallest Is that correct ?
Bro, I have written the same code as yours but I am having a doubt. why we are not breaking the loop..? we got the required solution. I tried this but it showed an error. if possible then please clear my doubt. @take U forward Code: class Solution { public: int kthSmallest(TreeNode* root, int k) { int i=0; int ans=0; TreeNode*curr; while(root) { if(!root->left) { i++; if(i==k) { ans= root->val; break; }
you said u have provided the code in the description but it isnt there, this is a very common occurence when i look at descrptions i never find the codes, am i looking at the wrong place or is he just not attaching the code
you are welcome: class Solution { int count=0; int result; public int kthSmallest(TreeNode root, int k) { if (root==null) { return 0; } inOrderTraversal(root,k); return result;
} public void inOrderTraversal(TreeNode root, int k) { if (root==null) { return ; } inOrderTraversal(root.left,k); count++; if (count==k) { result =root.val; return; } inOrderTraversal(root.right,k); } }
@@mridulsarma9022 toh wo beginner recursion ye sb me kse dkh skta h koi v ...hm ye bol rhe ki in sb ka dsa ka v ase hii playlist bnaye ...jse ki aapne graph,tree ka bnya h ye bol rhe h hm . bro..... Wse wo sb playlist ksa h qsns sb ka maine nii dkha h pura...kyuki meko abhi wo sb utna nii ata bhaii mere!!
thanks mate! this was really challenging & fun solving, tried to implement it using Moris Traversal without revising and took a while to implement but was able to implement it successsfully!
One of my friend's got rejection in amazon with morris traversal approach. How can you do this in only logN complexity? This was asked in amazon interview and the approach doesn't make sense. It was written that we can store a count of left subtree nodes while generating the tree. Generation will take o(n) itself then how can it be logN.
GFG article hai Method 2: Augmented Tree Data Structure (O(h) Time Complexity and O(h) auxiliary space) The idea is to maintain the rank(count) of each node. We can keep track of elements in the left subtree of every node while building the tree. Since we need the K-th smallest element, we can maintain the number of elements of the left subtree in every node. Assume that the root is having ‘lCount’ nodes in its left subtree. If K = lCount + 1, root is K-th node. If K < lCount + 1, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > lCount + 1, we continue our search in the right subtree for the (K - lCount - 1)-th smallest element. Note that we need the count of elements in the left subtree only.
List result; public int kthSmallest(TreeNode root, int k) { result = new ArrayList(); inorder(root,k); return result.get(result.size()-1); } private void inorder(TreeNode root,int k){ if(root==null) return; inorder(root.left,k); if(result.size()==k) return; result.add(root.val); inorder(root.right,k); }
int kthSmallest(TreeNode* root, int k) { vector v; helper(root,v,k); return v[k-1]; } the complexity is still O(min (k,n)) wont that will be more efficient
finally after this video, your face is in the video, video is booring without your face and newer version of you make thing more clear then older version of striver.
Can anyone Please ,explain to me why is it showing run-time error ,I m trying to do inorder morris traversal class Solution { public: int kthSmallest(TreeNode* root, int k) {
@@saarthaksharma9555 yeah, if we use break or return the construct of binary tree will change and cause to overflow, we have to run until the curr is null
In largest, we can traverse right node left and then apply the same logic..
You can also contribute an article for this video: takeuforward.org/contribute/help-us-grow-takeuforward/
Will be continuing with this setup, as youtube tends to push videos with human appearance!!
any plan of hiring interns for ur site and what will be the requirements
@takeUforward
Thank you so much anna🤩🤩🤩🤩🤩🤩.....
keep doing more and more videos anna....
For finding smallest using #InorderMorrisTraversal (left, root, right) :-
code🔥🔥🔥🔥🔥🔥:-
int kthSmallest(TreeNode* root, int k) {
TreeNode* cur = root;
int ans;
int count =0;
while(cur != nullptr){
if(cur -> left == nullptr){
count += 1;
if(count == k){
ans= cur -> val;
}
cur = cur -> right;
}
else{
TreeNode* prev = cur -> left;
while(prev -> right != nullptr && prev -> right != cur){
prev = prev -> right;
}
if(prev -> right== nullptr){
prev -> right = cur;
cur = cur -> left;
}
else{
count += 1;
prev -> right = nullptr;
if(count == k){
ans =cur -> val;
}
cur = cur -> right;
}
}
}
return ans;
}
for finding largest using #reversalInorderMorrisTraversal (right root left) :-
code🔥🔥🔥🔥🔥🔥:-
int kthLargest(Node* root, int k) {
Node* cur = root;
int ans;
int count =0;
while(cur != nullptr){
if(cur -> right == nullptr){
count += 1;
if(count == k){
ans= cur -> data;
}
cur = cur -> left;
}
else{
Node* prev = cur -> right;
while(prev -> left != nullptr && prev -> left != cur){
prev = prev -> left;
}
if(prev -> left== nullptr){
prev -> left = cur;
cur = cur -> right;
}
else{
count += 1;
prev -> left = nullptr;
if(count == k){
ans =cur -> data;
}
cur = cur -> left;
}
}
}
return ans;
}
for kth largest we can do a reverse inorder kind of thing: RIGHT ROOT LEFT with the counter logic
Yep
Yeah
Han bete
We can even find n-k+1 smallest for kth largest
Nice dp
One correction:
k th largest element = (n-k+1)th smallest element
Exactly! I was thinking about this
correct!
right. i was thinking the same.
For kth largest just do the reverse in-order , and print the kth element. Bcoz this will lead to decreasing order.
This is the first solution that comes in the mind
Just a small observation In the kth largest problem if we take reverse inorder than the elements are sorted in descending fashion, so we can directly get kth largest element
sahi hai!!
correct ✅
Of course ! but the optimal solution as he said is not to use any extra space. That's why n-k logic comes.
we can also do this by doing inorder traversal (this will make the vector in sorted format) and then finding the kth smallest no. in it. time complexity will be O(n) + O(n)
for Kth largest it should be (n-k+1)th smallest
Exactly! I was thinking about this
@@parthsalat right
For the kth largest question, we don't even need to make the adjustment as (n-k)th smallest element. We can simply reverse the order of traversal as - Right - Root - Left
so its post order right?
@@ChayK11 no, postorder traversal is: left->right->root
why not we visit directly right first and left after while treversing for k th max. :) it will be done in one treversal
Bhaiya it may be n+1-k th element..as for if we have 4 nodes then 2nd element from last will be 4+1-2 th i.e 3rd node.thats why I am saying about this confusion
ya same . It should be n+1-k
Yes
I think Kth largest element can be done in single traversal. By using reverse inorder traversal i.e.(Right-Node-Left) .Then we can easily figure out kth largest element in single traversal.
Just require few modification in code:
int kthLargest(TreeNode* root, int k) {
stack st;
TreeNode* node = root;
int cnt = 0;
while(true) {
if(node != NULL) {
st.push(node);
node = node->right;
}
else {
if(st.empty() == true) break;
node = st.top();
st.pop();
cnt++;
if(cnt == k) return node->val;
node = node->left;
}
}
return -1;
}
Yeah..
Don't write like this inside if condition st.empty()==true
You can just write if( st.empty() )
@@विशालकुमार-छ7त Actually it is not my code it is striver's code i just modify it for the largest
@@aayushprajapati347 oo...sorry
aeee red coder
Diwali pe DP Series aa rha hain kya ?
Understood.............Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
JAVA Solution for Smallest Kth: -
class Solution {
private int count = 0;
private int result = 0;
public int kthSmallest(TreeNode root, int k) {
traverse(root, k);
return result;
}
private void traverse(TreeNode node, int k) {
if (node == null) {
return;
}
traverse(node.left, k);
count++;
if (count == k) {
result = node.val;
return;
}
traverse(node.right, k);
}
}
JAVA Solution for Largest Kth: -
class Solution
{
int ans = 0;
int count = 0;
public int kthLargest(Node root,int k)
{
traversal(root,k);
return ans;
}
public void traversal(Node root, int k){
if(root == null) return;
traversal(root.right,k);
count++;
if(count == k){
ans = root.data;
return;
}
traversal(root.left,k);
}
}
If we use inorder then there will be no need of sorting… because inorder of bst is already sorted
If we do simple recursive inorder traversal then time complexity should be O(k) because we don't need to go further after getting kth smallest
Is that correct ?
Yes, but at most K is equal to n (e.g. k=n) . So, the worst case scenario is O(n).
worst case scenario would be O(N)
OP Video Quality and Setup🔥
Using Morris Inorder Traversal
TC - O(N), SC - O(1)
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int count = 0;
int ans;
TreeNode* curr = root;
while(curr){
if(curr->left == NULL){
count++;
if(count == k){
ans = curr->val;
}
curr = curr->right;
}
else{
TreeNode* prev = curr->left;
while(prev->right && prev->right != curr){
prev = prev->right;
}
if(prev->right == NULL){
prev->right = curr;
curr = curr->left;
}
else{
count++;
prev->right = NULL;
if(count == k){
ans = curr->val;
}
curr = curr->right;
}
}
}
return ans;
}
};
Bro, I have written the same code as yours but I am having a doubt. why we are not breaking the loop..? we got the required solution. I tried this but it showed an error. if possible then please clear my doubt.
@take U forward
Code:
class Solution {
public:
int kthSmallest(TreeNode* root, int k)
{
int i=0;
int ans=0;
TreeNode*curr;
while(root)
{
if(!root->left)
{
i++;
if(i==k)
{
ans= root->val;
break;
}
root=root->right;
}
else
{
curr=root->left;
while(curr->right && curr->right!=root)
curr=curr->right;
if(curr->right==root)
{
curr->right=NULL;
i++;
if(i==k)
{
ans= root->val;
break;
}
root=root->right;
}
else
{
curr->right=root;
root=root->left;
}
}
}
return ans;
}
};
@@Avinashkumar-km2cl Hey , i am also trying to break out of loop but getting error, if you got an answer then please help
@@Avinashkumar-km2cl because in morris traversal you did create threads and now you are not breaking it
@@factfactorial632 So we have to traverse the whole tree and can't break the loop, even if we got the answer at the very start!??
@@akshitsangwan_ got the answer anyone?
Is your tree series enough for DSA beginners for Tech interviews of companies like Microsoft , linkedin etc?
@Anna English thanks for letting me know
@Strawberry and Strings
you said u have provided the code in the description but it isnt there, this is a very common occurence when i look at descrptions i never find the codes, am i looking at the wrong place or is he just not attaching the code
you are welcome:
class Solution {
int count=0;
int result;
public int kthSmallest(TreeNode root, int k) {
if (root==null)
{
return 0;
}
inOrderTraversal(root,k);
return result;
}
public void inOrderTraversal(TreeNode root, int k)
{
if (root==null)
{
return ;
}
inOrderTraversal(root.left,k);
count++;
if (count==k)
{
result =root.val;
return;
}
inOrderTraversal(root.right,k);
}
}
He's providing quality content for free, and still you are complaining for a small mistake?
Thank you for the simple explanation
Man, I was stuck with this problem yesterday coz I didn't get what I have to find from all the tutorials online. Striver explained it in 2 mins.🔥
I can't believe you are in I.T
@@geekaffairs6475 I am not in IT, I am the IT.
@@geekaffairs6475 samw bro ye banda har jagah h
Best Series ever seen❤️❤️. Is CP necessary for CODING ROUND..??? PLS ANSWER 🙏🙏🙏
I did not understand why you need to sort the elements, if we do inorder traversal we could do it in o(n),
same doubt
Striver bhaiya aur kitne videos baki he playlist ke when it will be completed??
For largest why not do [Right,Node,Left] ?
when you were explaining the brut ,i accidentally coded the optimal by using morries xd
Can we do R N L for Kth largest using morris? I just tried a psuedo code seems possible.
what if duplicate elements are there
Ab yhi request h bhaiya..... recursion, backtracking,dp k v ase hii series alg alg dsa k upr lekr aaiye!! plzzz bhaiyaaa ❤️❤️❤️🥺🥺🙏🙏🙏
Check the playlists..I hope you will get all of those.
@@mridulsarma9022 nii bro bat wo nii h bhaiyaaa ne toh usme syd sde sheet ka sb video explain qsn sb ka dala hua h n ...
.
@@mridulsarma9022 toh wo beginner recursion ye sb me kse dkh skta h koi v ...hm ye bol rhe ki in sb ka dsa ka v ase hii playlist bnaye ...jse ki aapne graph,tree ka bnya h ye bol rhe h hm . bro.....
Wse wo sb playlist ksa h qsns sb ka maine nii dkha h pura...kyuki meko abhi wo sb utna nii ata bhaii mere!!
Keep doing this GOOD WORK
Great explanation bro. Perfectly explained all the possible solutions for this problem
shoudn't it be for kth largest we need n-k+1th smallest?????
yeah!!
thanks mate! this was really challenging & fun solving, tried to implement it using Moris Traversal without revising and took a while to implement but was able to implement it successsfully!
Nice dp...Daffodils, isn't it?
kth element can be found out in O(N) using quick sort
quick sort is nlogn bro
We just have to run quicksort partition function one time to find kth element
Not one time but a few times
It's called quick select
Why we need to sort?Inorder always gave sorted elements
we need to sort only if we're implementing preorder, postorder or level order.
Bhaiya this is the best evolution of your videos. Left side knowledge right side legend. It's f***king awesome bhaiya. 🙂🙂🙂
For kth largest we can do right root left traversal
Great explanation. Those last approaches are great.
One of my friend's got rejection in amazon with morris traversal approach. How can you do this in only logN complexity? This was asked in amazon interview and the approach doesn't make sense. It was written that we can store a count of left subtree nodes while generating the tree. Generation will take o(n) itself then how can it be logN.
complexity will be o(n) not logn, space complexity will be o(1)
@@ideepakpandey thats what i said read the comment again
GFG article hai
Method 2: Augmented Tree Data Structure (O(h) Time Complexity and O(h) auxiliary space)
The idea is to maintain the rank(count) of each node. We can keep track of elements in the left subtree of every node while building the tree. Since we need the K-th smallest element, we can maintain the number of elements of the left subtree in every node.
Assume that the root is having ‘lCount’ nodes in its left subtree. If K = lCount + 1, root is K-th node. If K < lCount + 1, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > lCount + 1, we continue our search in the right subtree for the (K - lCount - 1)-th smallest element. Note that we need the count of elements in the left subtree only.
C++ Solution
class Solution {
public:
void helper(TreeNode *root,int &k,int &count,int &ans)
{
if(root==NULL)
return;
helper(root->left,k,count,ans);
count++;
if(count==k)
ans=root->val;
helper(root->right,k,count,ans);
}
int kthSmallest(TreeNode* root, int k) {
int count=0,ans;
helper(root,k,count,ans);
return ans;
}
};
Understood. Thanks
New setup is good .... But I don't think it matters much .... For me your content matters more and it's great
Striver's video explanation --- mind blown
Striver's video explanation with face cam ---- mind blown ultra pro max 😂😂
tysm sir
LeetCode 230:
class Solution {
public:
int count = 0;
int ans;
void inorder(TreeNode* root, int k){
if(!root)return;
inorder(root->left,k);
if(++count==k){
ans = root->val;
return;
}
inorder(root->right,k);
}
int kthSmallest(TreeNode* root, int k) {
inorder(root,k);
return ans;
}
};
Thanks bro!
We can also add condition like.... To increase the count value only when there's some value there and not NULL like
if(root)
if (++count==k)
@@VishalGupta-xw2rp But we already checked for the root, then root can't be null. So no need to check for it.
If (ans!=-1) return ans; will it save something?
shouldn't kth largest should be n-k+1 ??? Anyone?
Thodi mehnat lag gyi Morris implement krne me, but golden content!
can you please provide the morris traversal solution ? i'm getting stack overflow error 🥹🥹
Understood
C++ Code :
class Solution {
public:
vectorans;
void inorder(TreeNode* root){
if(root == NULL ) return;
inorder(root->left);
ans.push_back(root->val);
inorder(root->right);
}
int kthSmallest(TreeNode* root, int k) {
inorder(root);
return ans[k-1];
}
};
morris traversal for kth largest and "dec" vector in program stores decreasing order of values
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int cnt=0;
TreeNode * curr=root;
int ans;
vector dec;
while(curr!=NULL)
{
if(curr->right==NULL)
{
cnt++;
if(cnt==k)
{
ans=curr->val;
}
dec.push_back(curr->val);
curr=curr->left;
}
else{
TreeNode * temp=curr->right;
while(temp->left!=NULL && temp->left!=curr)
temp=temp->left;
if(temp->left==NULL){
temp->left=curr;
curr=curr->right;}
else{
temp->left=NULL;
cnt++;
if(cnt==k)
{
ans=curr->val;
}
dec.push_back(curr->val);
curr=curr->left;
}
}
}
for(int ele:dec)
cout
Thank you sir
Agar ek din pehle upload kr deta bhai toh mera amazon clear ho jata..
Haan kal hi kia tha upload
What was asked to you.
need to improve this video. not very clear
understood
List result;
public int kthSmallest(TreeNode root, int k) {
result = new ArrayList();
inorder(root,k);
return result.get(result.size()-1);
}
private void inorder(TreeNode root,int k){
if(root==null) return;
inorder(root.left,k);
if(result.size()==k) return;
result.add(root.val);
inorder(root.right,k);
}
understood.
Amazing explanation.
explanation on point . loved it bhaiya
class Solution {
public:
void inorder(TreeNode* root,int &c,int &k,int &ans){
if(!root)return;
inorder(root->left,c,k,ans);
c++;
if(c==k){ans=root->val; return;}
inorder(root->right,c,k,ans);
}
int kthSmallest(TreeNode* root, int k) {
int c=0;
int ans;
inorder(root,c,k,ans);
return ans;
}
};
we can add if(c>k) return;
before root->right;
Man, after DP, make a series on stack & queue..
Thank you
Thanks bro, you did good
Understood thanks :)
striver video is like the latest iPhone top notch but with facecam It is like u get air pods and fast charger in the box with the latest apple cloth.
Ab maza aayega na bidu💝👍
06:40 Largest
what if we perform an in order traversal as it will be automatically sorted
void helper(TreeNode* root,vector & v,int k){
if(v.size()==k||root==NULL)
return;
helper(root->left,v,k);
v.push_back(root->val);
helper(root->right,v,k);
}
int kthSmallest(TreeNode* root, int k) {
vector v;
helper(root,v,k);
return v[k-1];
}
the complexity is still O(min (k,n))
wont that will be more efficient
time complexity will be O(N), since we have to go to every node if we are storing in vector
kth largest=(n-k+1)th smallest element.
Thank you bhaiya Meet me in G.😎😎😎😎
we love your content and we love you...🖤
4:25
Understood
Using Morris Traversal
class Solution {
public:
Node* inorder(Node* root, int &K){
Node* curr = root;
while(curr != NULL){
if(curr->left == NULL){
K--;
if(K==0) return curr;
curr = curr->right;
}
else{
Node* prev = curr->left;
while(prev->right != NULL && prev->right != curr){
prev = prev->right;
}
if(prev->right == NULL){
prev->right = curr;
curr = curr->left;
}
else{
prev->right = NULL;
K--;
if(K==0) return curr;
curr = curr->right;
}
}
}
return NULL;
}
// Return the Kth smallest element in the given BST
int KthSmallestElement(Node *root, int K) {
// add code here.
Node* res = inorder(root, K);
if( res != NULL)
return res->data;
return -1;
}
};
it isnt giving error on leetcode?
understand ❤
understood
finally after this video, your face is in the video, video is booring without your face and newer version of you make thing more clear then older version of striver.
That makes sense
Can anyone Please ,explain to me why is it showing run-time error ,I m trying to do inorder morris traversal
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int freq=0;
TreeNode* ans;
if(root==NULL)return 0;
TreeNode* curr=root;
while(curr!=NULL){
if(curr->left==NULL){
freq++;
if(freq==k){
return curr->val;
break;
}
curr=curr->right;
}
else{
TreeNode* temp=curr->left;
while(temp->right!=NULL && temp->right!=curr)
temp=temp->right;
if(temp->right==NULL){
temp->right=curr;
curr=curr->left;
}
else{
//temp->right=NULL;
freq++;
if(freq==k){
return curr->val;
}
temp->right=NULL;
curr=curr->right;
}
}
}
return -1;
}
};
else{
//temp->right=NULL;
freq++;
if(freq==k){
return curr->val;
}
temp->right=NULL;
curr=curr->right;
Here you are trying to edit the BST, maybe that's the issue
You have to return integer answer but you are returning 'node' so just put the condition that when freq==k,
ans=cur->val;
and at the end return ans;
and don't apply the break statement as it will give stack overflow error because of the morris threading
@@saarthaksharma9555 yeah, if we use break or return the construct of binary tree will change and cause to overflow, we have to run until the curr is null
#Striveronfire 🔥🔥🔥
us..
C++ code link opens Javacode and Java code link opens C++ code. Edit That Bro 😇
done!
💚
"us"
int inorderTraversal(TreeNode* root, int k) {
TreeNode* curr = root;
int cnt=0;
while(curr)
{
if(curr->left==NULL)
{
cnt++;
if(k==cnt) return curr->val;
curr=curr->right;
}
else
{
TreeNode* prev = curr->left;
while(prev->right && prev->right!=curr)
{
prev = prev->right;
}
if(prev->right==NULL)
{
prev->right=curr;
curr=curr->left;
}
else
{
prev->right=NULL;
cnt++;
if(k==cnt) return curr->val;
curr=curr->right;
}
}
}
return -1;
}
int kthSmallest(TreeNode* root, int k) {
if(root==NULL) return -1;
return inorderTraversal(root , k);
}
for this code im getting the following error
AddressSanitizer:DEADLYSIGNAL
=================================================================
==22==ERROR: AddressSanitizer: stack-overflow on address 0x7ffea2a00ff8 (pc 0x564fc93607d9 bp 0x7ffea2a01010 sp 0x7ffea2a01000 T0)
#0 0x564fc93607d9 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x1a87d9)
#1 0x564fc9360800 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x1a8800)
#2 0x564fc9360800 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x1a8800)
#3 0x564fc93607dd in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x1a87dd)
#4 0x564fc9360800 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x1a8800)
#5 0x564fc9360800 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x1a8800)
#6 0x564fc93607dd in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x1a87dd)
Finally 🔥
I am getting runtime error in Leetcode everytime while doing through Morris Traversal
int kthSmallest(TreeNode* root, int k) {
if(root == NULL) return -1;
int cnt=0;
TreeNode* curr = root;
TreeNode* temp;
while(curr){
if(curr -> left == NULL){
temp = curr;
cnt++;
curr = curr -> right;
}
else{
TreeNode* pred = curr -> left;
while(pred -> right && pred -> right != curr)
pred = pred -> right;
if(pred -> right == NULL){
pred -> right = curr;
curr = curr -> left;
}
else{
pred -> right = NULL;
temp = curr;
cnt++;
curr = curr -> right;
}
}
if(cnt == k){
return temp -> val;
}
}
return -1;
}
Can anyone correct it?
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int count = 0;
int ans;
TreeNode* curr = root;
while(curr){
if(curr->left == NULL){
count++;
if(count == k){
ans = curr->val;
}
curr = curr->right;
}
else{
TreeNode* prev = curr->left;
while(prev->right && prev->right != curr){
prev = prev->right;
}
if(prev->right == NULL){
prev->right = curr;
curr = curr->left;
}
else{
count++;
prev->right = NULL;
if(count == k){
ans = curr->val;
}
curr = curr->right;
}
}
}
return ans;
}
};
@@zanies6288 then this is not O(K) it becomes O(N)
💝💙💝
Coolm
.....................
reach++
im the 400 like
One correction:
k th largest element = (n-k+1)th smallest element
Exactly! I was thinking about this
understood
Understood
understood
understood
Understood
understood