L45. K-th Smallest/Largest Element in BST

[@takeUforward]

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!!

[@solaris413]

any plan of hiring interns for ur site and what will be the requirements

[@ananthalakshmi]

@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; }

[@deanwinchester8691]

for kth largest we can do a reverse inorder kind of thing: RIGHT ROOT LEFT with the counter logic

[@SouravGhosh-yb1ee]

Yep

[@lokeshrajput2458]

Yeah

[@kinshuk1743]

Han bete

[@nikhilmeena8585]

We can even find n-k+1 smallest for kth largest

[@parthsalat]

Nice dp

[@GauravKumar-dw2ml]

For kth largest just do the reverse in-order , and print the kth element. Bcoz this will lead to decreasing order.

[@secondarypemail7181]

This is the first solution that comes in the mind

[@mohdhammadsiddiqui7598]

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

[@yagniktalaviya2146]

sahi hai!!

[@amanali9501]

correct ✅

[@peacefullife2071]

Of course ! but the optimal solution as he said is not to use any extra space. That's why n-k logic comes.

[@parikshitsinghrathore6130]

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)

[@akshaychavan5511]

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

[@ChayK11]

so its post order right?

[@wttc4]

@@ChayK11 no, postorder traversal is: left->right->root

[@vaishnavigour5777]

for Kth largest it should be (n-k+1)th smallest

[@parthsalat]

Exactly! I was thinking about this

[@viveknagar4537]

@@parthsalat right

[@UdayKumar-tm1fb]

Nooo

[@stith_pragya]

Understood.............Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@kushagraahire1871]

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); } }

[@kushagrakulshrestha2966]

Nice name bro

[@budhadityachatterjee6270]

Diwali pe DP Series aa rha hain kya ?

[@abcsumits]

why not we visit directly right first and left after while treversing for k th max. :) it will be done in one treversal

[@aayushprajapati347]

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; }

[@takeUforward]

Yeah..

[@विशालकुमार-छ7त]

Don't write like this inside if condition st.empty()==true You can just write if( st.empty() )

[@aayushprajapati347]

@@विशालकुमार-छ7त Actually it is not my code it is striver's code i just modify it for the largest

[@विशालकुमार-छ7त]

@@aayushprajapati347 oo...sorry

[@kaushikkumarbora]

aeee red coder

[@shantanugupta-oz1dx]

Thank you for the simple explanation

[@xavier6955]

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.🔥

[@geekaffairs6475]

I can't believe you are in I.T

[@xavier6955]

@@geekaffairs6475 I am not in IT, I am the IT.

[@utkarshverma2604]

@@geekaffairs6475 samw bro ye banda har jagah h

[@divyanshusingh2396]

If we use inorder then there will be no need of sorting… because inorder of bst is already sorted

[@mridulsarma9022]

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

[@aditisneh6420]

ya same . It should be n+1-k

[@jayanth1191]

Yes

[@ishankbansal9239]

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; } };

[@Avinashkumar-km2cl]

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; } };

[@mayankkumar6067]

@@Avinashkumar-km2cl Hey , i am also trying to break out of loop but getting error, if you got an answer then please help

[@factfactorial632]

@@Avinashkumar-km2cl because in morris traversal you did create threads and now you are not breaking it

[@akshitsangwan_]

@@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!??

[@mukib_khan_]

@@akshitsangwan_ got the answer anyone?

[@ahustler110]

but why will we sort?? inorder of bst is already sorted array in incresing order

[@AbhishekPandey-dj2eo]

Keep doing this GOOD WORK

[@sagarkakkar4150]

kth element can be found out in O(N) using quick sort

[@mayanksardana3179]

quick sort is nlogn bro

[@sagarkakkar4150]

We just have to run quicksort partition function one time to find kth element

[@sagarkakkar4150]

Not one time but a few times It's called quick select

[@ankittjindal]

Ab yhi request h bhaiya..... recursion, backtracking,dp k v ase hii series alg alg dsa k upr lekr aaiye!! plzzz bhaiyaaa ❤️❤️❤️🥺🥺🙏🙏🙏

[@mridulsarma9022]

Check the playlists..I hope you will get all of those.

[@ankittjindal]

@@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 ... .

[@ankittjindal]

@@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!!

[@pranshumehta3228]

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 ?

[@dianafarhat9479]

Yes, but at most K is equal to n (e.g. k=n) . So, the worst case scenario is O(n).

[@imPriyansh77]

worst case scenario would be O(N)

[@arjunkurariya2235]

Best Series ever seen❤️❤️. Is CP necessary for CODING ROUND..??? PLS ANSWER 🙏🙏🙏

[@shivangisrivastava1158]

Thodi mehnat lag gyi Morris implement krne me, but golden content!

[@Stickman-rz9nu]

can you please provide the morris traversal solution ? i'm getting stack overflow error 🥹🥹

[@rakhshanahmad8057]

Great explanation. Those last approaches are great.

[@izumi7754]

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

[@anishaa3298]

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); } }

[@rushidesai2836]

He's providing quality content for free, and still you are complaining for a small mistake?

[@prasannamalatesha3887]

Great explanation bro. Perfectly explained all the possible solutions for this problem

[@ANANDKUMAR-hd8mj]

nice concept

[@AlokSingh-qj3hf]

class Solution(object): def __init__(self): self.c = 0 self.r = 0 def kthSmallest(self, root, k): """ :type root: TreeNode :type k: int :rtype: int """ def inor(k,c,root): if root==None: return inor(k,c,root.left) self.c+=1 if k==self.c: self.r=root.val return inor(k,c,root.right) inor(k,self.c,root) return self.r

[@abhijitroy1958]

when you were explaining the brut ,i accidentally coded the optimal by using morries xd

[@aryanchaurasia1081]

For kth largest we can do right root left traversal

[@tanveer.shaikh]

I did not understand why you need to sort the elements, if we do inorder traversal we could do it in o(n),

[@alliswellbrochill9937]

same doubt

[@tech_wizard9315]

Is your tree series enough for DSA beginners for Tech interviews of companies like Microsoft , linkedin etc?

[@tech_wizard9315]

@Anna English thanks for letting me know

[@vedantsharma5876]

@Strawberry and Strings

[@alesblaze4745]

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!

[@parthsalat]

Nice dp...Daffodils, isn't it?

[@sparshsharma3150]

Striver's video explanation --- mind blown Striver's video explanation with face cam ---- mind blown ultra pro max 😂😂

[@mayankbisht1277]

For largest why not do [Right,Node,Left] ?

[@sushantbhosale5792]

Striver bhaiya aur kitne videos baki he playlist ke when it will be completed??

[@Usurperhk]

Bhaiya this is the best evolution of your videos. Left side knowledge right side legend. It's f***king awesome bhaiya. 🙂🙂🙂

[@ChetanSingh-zp4ct]

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; } };

[@herculean6748]

Thanks bro!

[@VishalGupta-xw2rp]

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)

[@yativishnoi5110]

@@VishalGupta-xw2rp But we already checked for the root, then root can't be null. So no need to check for it.

[@only_for_fun1234r]

If (ans!=-1) return ans; will it save something?

[@akshayteja2864]

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; } };

[@abhinavkumar6584]

shouldn't kth largest should be n-k+1 ??? Anyone?

[@JEAnandkumar]

One correction: k th largest element = (n-k+1)th smallest element

[@parthsalat]

Exactly! I was thinking about this

[@dingo_5998]

Thank you bhaiya Meet me in G.😎😎😎😎

[@codeman3828]

Understood. Thanks

[@sahil_bagde]

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]; } };

[@reddysasikiran315]

what if duplicate elements are there

[@KnowledgeofEverything]

New setup is good .... But I don't think it matters much .... For me your content matters more and it's great

[@AnandSingh-zm5cm]

Why we need to sort?Inorder always gave sorted elements

[@imPriyansh77]

we need to sort only if we're implementing preorder, postorder or level order.

[@aryansinha1818]

06:40 Largest

[@sakshamsengar9798]

shoudn't it be for kth largest we need n-k+1th smallest?????

[@imPriyansh77]

yeah!!

[@anshulgoel1940]

Can we do R N L for Kth largest using morris? I just tried a psuedo code seems possible.

[@isheep9025]

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

[@naman_goyal]

Ab maza aayega na bidu💝👍

[@hitenrana4775]

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.

[@ideepakpandey]

complexity will be o(n) not logn, space complexity will be o(1)

[@hitenrana4775]

@@ideepakpandey thats what i said read the comment again

[@Rajat_maurya]

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.

[@vishious14]

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); }

[@ankitkr09]

Agar ek din pehle upload kr deta bhai toh mera amazon clear ho jata..

[@takeUforward]

Haan kal hi kia tha upload

[@nandinisugandhi748]

What was asked to you.

[@MadhavGupta-fi2tu]

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; } };

[@DeepakKumar-mn8yi]

we can add if(c>k) return; before root->right;

[@shubamgoswami]

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.

[@pvenkatesh3690]

It's looking kth largest approach is wrong. it should be Kth largest = (N-K) + 1 smallest element

[@geekaffairs6475]

Amazing explanation.

[@VIRAJBHOSLE]

need to improve this video. not very clear

[@santoshkumarroy5070]

explanation on point . loved it bhaiya

[@lavanyaprakashjampana933]

we love your content and we love you...🖤

[@adityapandey23]

Understood

[@shouvikdatta6831]

Man, after DP, make a series on stack & queue..

[@mohitsingh7793]

kth largest=(n-k+1)th smallest element.

[@KartikeyTT]

tysm sir

[@vaalarivan_p]

4:25

[@UECAshutoshKumar]

Thank you sir

[@ShubhanshuG007]

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; } };

[@divyanshjain7999]

it isnt giving error on leetcode?

[@sankalpietechtips]

Thanks bro, you did good

[@harshitjaiswal9439]

understood.

[@Girish415]

Thank you

[@chiragbansod8252]

understood

[@Anonymous-uj3jx]

Understood thanks :)

[@saurabhgautam2697]

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; } };

[@adityan5302]

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

[@saarthaksharma9555]

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;

[@saarthaksharma9555]

and don't apply the break statement as it will give stack overflow error because of the morris threading

[@ThoNguyenuc-pz3yr]

@@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

[@aditya-st1sv]

#Striveronfire 🔥🔥🔥

[@shantipriya370]

us..

[@saumyakarnwal7551]

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

[@mdshaqlain3252]

time complexity will be O(N), since we have to go to every node if we are storing in vector

[@mehulmorker258]

C++ code link opens Javacode and Java code link opens C++ code. Edit That Bro 😇

[@roopeshn3301]

Understood

[@sundarbsr4275]

understand ❤

[@suvanshmahajan5902]

"us"

[@anubhavverma7193]

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)

[@shashankojha3452]

That makes sense

[@purushottam108]

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.

[@NikhilGupta-zo5jh]

understood

[@adityaprakash1172]

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?

[@zanies6288]

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; } };

[@divyanshjain7999]

@@zanies6288 then this is not O(K) it becomes O(N)

[@momilijaz271]

done!

[@KaushikSharma-c3q]

.....................

[@preetikushwaha8734]

Finally 🔥

[@ajayypalsingh]

💚

[@p38_amankuldeep75]

💝💙💝

[@piyushacharya7696]

reach++

[@Girish415]

Coolm

[@SHASHANKRUSTAGII]

im the 400 like

[@JEAnandkumar]

One correction: k th largest element = (n-k+1)th smallest element

[@parthsalat]

Exactly! I was thinking about this

[@ayushkushwaha171]

correct!

[@khushududeja2183]

right. i was thinking the same.

[@sibiranganath]

Understood

[@abhinanda7049]

understood

[@VikasGupta-ok9lh]

Understood