Find Kth Largest and Kth Smallest element in a BST | Binary Search Tree | DSA Sheet | Amazon 🔥

#bst #binarysearchtree #competitiveprogramming #coding #dsa
Hey, Guys in this video I have explained how we can solve the problem 'Find Kth Largest and Kth Smallest element in a BST'.

In our another channel we have started DSA with C++ course and Programming with Python course for FREE. You can check it out.


Join our Telegram Channel for more Information

🔰 Get 10% OFF on all GeeksforGeeks Courses
Coupon Code = CODELIBRARY

Follow us on Instagram:

Follow us on LinkedIn:

Hope you like it. Comment if you have any doubt

LIKE | SHARE | SUBSCRIBE

[amitperane]

if k ander k==idx hai to idx++ kyu kiya hai return bhi to kr rhe hai ??

[helloUser]

For time complexity O(k), these lines should be there, to stop the further calls for the right subtree.
if(k==cnt) {
ans = root->data;
cnt++;
return;
}
if (cnt>k) {
return;
} else {
cnt++;
}

[tanvisharma]

Very lucid explanation. Excellent job keep going:))

[AvishekPaulOnline]

How is the time complexity O(k) here? If I print a "*" in the 1st line of solve() function, it prints the * 14 times which denotes that the entire tree has been traversed . Example tree - 4 2 6 1 3 5 7 N N N N N N N N k=1. If this is just an inorder traversal, it will go through the entire tree right? We are just doing the inorder traversal and printing when k is matching with counter (idx). But we are not stopping further function calls. 14 times * printing is a proof that the full tree is traversed (along with the function calls made for the null children)

[shishirkakhandki]

Can you pls explain why are you doing idx++ before returning in if block?

[srinivaskonduri]

Should have thought morris traversal as it was mention O(1) space. Very good explanation but can u teach the Morris Traversal of the BST.

[ravulaakhilsurya]

Bhai reading code vlogs banalo plz
So that we do get trained of reading code 🙋🙋🙋
I guess definately this idea makes your channel to grow faster...

[shubhmehrotra]

in if condition why did you use idx++ in if condition?

[harshitsharma]

great explaination brother but if u also clarify why u are doing idx++ in if condition it will be more perfect

[subhamkumar]

kth smallest this will work
class Solution {
public:
// Return the Kth smallest element in the given BST
int inorder(Node* root, int &i, int k)
{
if(root==NULL)
return -1;

int left=inorder(root->left, i, k);
if(left!=-1)
return left;
i++;
if(i==k)
return root->data;
return inorder(root->right, i, k);
}
int KthSmallestElement(Node *root, int k) {
// add code here.
int i=0;
int x=inorder(root, i, k);
return x;
}
};

[ravulaakhilsurya]

Bro how your editing driver code of gfg for few videos I am not getting how your doing it??

[gulshanrajput]

When it will come back then it's not back out it will running remaining nodes because when we come back then cout value will decrease so it's will increase again for remaining right node
For Example
50
/ \
30 60
/ \
25 35
/ \ / \
20 28 32 36

When we will back the on 30 then count is 1 then 30 will call it's right that is 35 ->32 so on and count will. Increase again

Any one agree with me...??

[suyashlokhande]

why no one explaining follow up question

[dhruvkaran]

It feels really good when u have solved this question and came to see that legends and mine thought match or not :D

[gauravshukla]

why we are increasing count of idx when we found out that

[adilkevin]

Possibly your code doesn't work correctly for multiple test-cases (TCs).

The first test case where your code failed:

Input:

78 69 80 4 72 79
5



Its Correct output is:

69



And Your Code's output is:

79


int ans;
void solve(Node* root, int k, int &idx)
{
if(!root) return;
solve(root->left, k, idx);
if(k==idx)
{
ans=root->data;
idx++;
return;
}
else idx++;
solve(root->right, k, idx);
}
int kthLargest(Node *root, int K)
{
int idx=1;
ans=-1;
solve(root, K, idx);
return ans;
}

[sigma]

this is not optimised we can do in o(h)

[amitabhchoudhury]

Bhaiya stacks and queues kab start karege ???

[swasthiknayak]

I guess space complexity for kth smallest is O(n), because we are basically doing inorder traversal of the binary tree, and not dividing the tree like we do for searching.

[surajpatil]

bro could you please explain why you are passing idx by reference and not by value?