Kth Smallest Element in a BST | Leetcode

This video explains a very important problem which is to find the Kth smallest element in a binary search tree. This is a very common programming interview question for most companies and it can be solved by many techniques. I have shown 3 methods to solve this in increasing order of optimizations. The first method is the simplest which is done just by inorder traversal and storing the elements in an array and returning the (K-1)th index element as answer. The second method uses recursion/stack to solve the problem. The third method is the most optimized approach and it uses a special BST property to find the Kth smallest element in just O(Height) time. I have also explained the CODE at the end of the video. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
LinkedIn: / surya-pratap-kahar-47b...
CODE LINK: gist.github.com/SuryaPratapK/...
SIMILAR PROBLEMS:
Kth largest element in an array: • Kth largest element in...
Check if a tree is bst or not: • Check if a tree is bst...

[@ayushupadhyaya7656]

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.

[@kshitijsharma6471]

Your second method is basically inorder traversal with slight modification. This modification is helpful in reducing time complexity. Nice approach bro👌👌👌

[@techdose4u]

Yes 👍

[@utsavjayaswal4701]

it imporves space complexity as well........in first method o(n) space was req. in 2nd o(1)

[@satyanarayanaguggilapu3735]

Thank you sir for your help. Vey well taught.

[@pranavsharma7361]

I like your work, I have referred to your video a lot. Keep it up

[@techdose4u]

Thanks :)

[@abhishekdhok5245]

Nice explanation... can u tell me which software you are using for teaching?

[@fatimajaffal9843]

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

[@techdose4u]

Multiple approaches!! Nice :)

[@amruthap6334]

i also used 1st apporach but i think it is not optimized...

[@adarshkashyap8715]

@@amruthap6334 yes ,since it uses extra spaces for vector

[@ds_world2468]

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

[@techdose4u]

Thanks :)

[@ChandraShekhar-by3cd]

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

[@techdose4u]

Yea will continue after this month.

[@ArpitDhamija]

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 ?

[@dhruv2014]

Nice code 🔥🔥🔥

[@amoghsinkar7489]

Could you also make videos involving concepts like trees, graphs..etc. and not only questions. It would be great if you do this

[@techdose4u]

Yes I will. But let this contest end 😅

[@spetsnaz_2]

I think he will be able to make videos after this May Challenge only 😀

[@techdose4u]

Yes correct

[@agileprogramming7463]

No I would actually prefer this as solutions of such high quality are rare on KZbin.

[@abhireddy8164]

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.

[@elasingh3151]

Your explanations are really good!

[@techdose4u]

Thanks 😊

[@manthankhorwal1477]

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

[@techdose4u]

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.

[@amoghsinkar7489]

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♥️.

[@techdose4u]

Thanks :)

[@surbhitamrakar1638]

Your explanations are always great:)

[@techdose4u]

Thanks

[@pj-xv3jk]

Hi, do you have an idea about the follow up quesiton of 230? the official answer is like sht

[@nagashayanr5940]

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]

👍

[@bibhu_107]

very nicely explained

[@techdose4u]

Thanks :)

[@amruthap6334]

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 ?

[@xapeuuu]

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

[@techdose4u]

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.

[@amruthap6334]

@@techdose4u but we cant use that approach.. thanx ...

[@techdose4u]

Yes we cannot because we are not allowed to modify nodes.

[@codeminatiinterviewcode6459]

can u please tell me what does this means int left = check(root->left, k);

[@codeminatiinterviewcode6459]

And also how to take these things while solving recursion.

[@ibrahimshaikh3642]

Well done 👌

[@techdose4u]

Thanks :)

[@ibrahimshaikh3642]

Where do u work

[@paragroy5359]

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

[@mdisi5967]

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.

[@crankyinmv]

I implemented approach 2 and got 19.54% on the time. I was hoping you had something better.

[@techdose4u]

I got 98.23% for my code. If you can see the submissions then everyone have used either stack or recursion.

[@crankyinmv]

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

[@lokeshgupta7770]

what will be the complexity of 1st approach?

[@techdose4u]

O(N)

[@programmingstuff5741]

Bro please. Explain perfect square GOOGLE KICKSTART question

[@techdose4u]

I think you meant perfect subarray correct??

[@programmingstuff5741]

@@techdose4u yes bro When will u expalin

[@techdose4u]

Planning this weekend only....

[@programmingstuff5741]

@@techdose4u thanks bro for making such efforts

[@intezaralam9357]

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)

[@harshitrathi6764]

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

[@shreedharkushwaha3100]

It gives wrong ans (0) for [5,3,6,2,4,null,null,1] 3. input but correct ans is 3 why??

[@ankurgupta4696]

Awsm i understood the concept

[@techdose4u]

Nice :)

[@venkatasaipreetamkotteda9388]

Is it a glitch or what ? Many videos of this playlist has only this video

[@punjabicodingstyle5111]

in second method how 6 is smallest element

[@surbhitamrakar1638]

It's not the smallest element it's the 5th smallest element in bst

[@rajeshbammidy180]

I have used In order:github.com/RajeshAatrayan/InterviewPreparation/blob/master/src/Trees/KthSmallestElementinaBST.java

[@techdose4u]

👍

[@ankurgupta4696]

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

[@SuganthanMadhav]

Why you are doing (k-1) == 0

[@aayush5474]

indexing starts from 0

[@settyruthvik6236]

# 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)

[@subhadippatra7930]

There are many repeated videos in this playlist.

[@techdose4u]

I don't really know about this bug but today I corrected may challenge playlist. I will check again.