for those who wonder why we are looking for curr->left in InOrder Successor answer : if we look in curr->right then we will be looking for values that are > curr->data and if we look in curr->left we will get values < curr->data, and ofcourse we want to replace the parent node with a value less than the curr->data to preserve the BST property i.e (parent->left->data < parent->data < parent->right->data)
anyone wondering why we are looking for curr->left, look before we are calling inorderSucc for root->right, means we are looking for all elements greater than root, and we want the least value thats greater than root, and thatll be present in the left most element of the subtree with node root->right
In the first go i had not understood anything because I had not took pan paper with me. After 2 days somehow I came again and now i had pen and paper with me and broke problem in 4 sub problem and tried each individually as new question : 1.Delete a leaf node in bst 2. Delete node with one child 3. Delete node with two child 4. Find inorder successor of a node in bst And now this problem seems very easy as compared to 1st time. Conclusion: untill you don't use pen paper you can't able solve problems exception are there for super minded peoples.
This is why Search in BST is depend on Height. Consider BST as below :- 1 2 3 4 5 Here height is N so time complexity is O(N) So Actual Time complexity of BST search: O(H) Average case Time complexity: O( log N )
1. Best case will be O(1), when we get element at roor itself 2. Average case will O(logn), when we search element in either left or right sub tree 3. Worst case will be O(n), when the BST have only one direction subtree in its child
sure these videos are helpful, but for people having good experince with recursion. For a lot of people including me, we have a hard time understanding the logic of how and why exactly the code was written the way it is. It would be really great if you also give a line by line explanation plus line by line example to show how the code works, specifically the recursion part.
for those who wonder why we are looking for curr->left in InOrder Successor ans: if we look from curr->left and curr->right both are similar to delete you can dry run the code by writing curr->right instead of curr->left ans will be same
Did anyone notice she said :"humein phele se pata hai time complexity of search in BST is o(n) thats is why we can say that time complexity in seacrh in BST is o(n)" ...kya ghumaya hai shabdo mei 😂😂😂 "great work"👍
Plz koi iss ka code bata du Write down a program to store values in binary search tree. Program should keep taking values until we enter values less than 100. After entering values, print all unique values in
If i try to delete each node one by one by perform delete function for all nodes and then if i print the inorder traversal still it prints the last element which i delete. Why?? Plz reply ....
"The successor will be the left most child of the right subtree or right child itself". Here in case 3 we are passing the argument [inorderSucc(root->right)] , hence we are going to the leftmost child of the right subtree. That's why we are progressing till curr->left != NULL. P.S- We are going till the leftmost child of RIGHT subtree because it would be the element just after the curr node in "inorder" sequence
Answer is NO! if inorder succ. happens to be a left child (at the right side of root offcourse)..if it has right child only...then passing the function remains only option.
this is giving me an error, let's suppose a tree 5 / \ 3 10 / \ / 2 4 9 / 8 so, when I'm deleting 9, 8 is also being deleted, and when I'm deleting 10, 9, and 8 are also being deleted, whereas, if I delete 3 or 5, they are displaying everything fine. IDK, if it's something with the code or just my personal error, as we're told that if we're deleting a node with 1 child, I'm supposed to relate, its parent to the child of the node being deleted. I don't see that happening. but as i said, it can be due to some sort of personal error, if someone can decode my problem. i'll be glad.
when key is smaller than root->data, we have to go in root->left to find the key and then delete it. After deletion temp is returned which will be joined to root->left , therefore we are taking the return from deleteinbst(root->left,key) in root->left
Can anyone share the code...., I am getting error in inorderSuccessor (not declared in scope). Watched the lecture twice but still not able to debug it.
it works all good. But whenever i try to delete the last root node available in the tree with no child, am unable to perform anymore functions and the program just closes itself.. like for e.g after deleting all the nodes, i call the delete function again, instead of gettin message "tree is empty" my program just stops executing itself. if anyone knows anything regarding this then let me know :) thanks
bhai kyuki inorder sequence hamesha sorted order of elements dega aur left tak isliye jaana hai kyuki bst ke properties ke hisaab se left me hi hame chote values milenge aur inorder me bhi yahi hota hai.So not to break the rules of binary search trees
"The successor will be the left most child of the right subtree or right child itself". Here in case 3 we are passing the argument [inorderSucc(root->right)] , hence we are going to the leftmost child of the right subtree. That's why we are progressing till curr->left != NULL. P.S- We are going till the leftmost child of RIGHT subtree because it would be the element just after the curr node in "inorder" sequence.
@@anonymous.u.s.e.r bhai koi difference nhi hai....jo tu c mei kr skta hai vo sab c++ mei kr skta hai...!! thoda bhot internal functioning mei farq hota hai...thoda bhot syntax mei....pr vhi cheez hai almost
@@shubhsahu4780 NO average case is o(logn) because in most of the cases we gonna have both left and right subtree but in the worst case, either left or right subtree will be NULL and the element I have to search will be the last node of that subtree
bro what about second child of 1 ? what if one already had 2 children for example 3 and 5, then if 3 is deleted we cant make 2 and 4 as children of 1 bcoz it already have 5 as 1 of its child.
bro what about second child of 1 ? what if 1 already had 2 children for example 3 and 5, then if 3 is deleted we cant make 2 and 4 as children of 1 bcoz it already have 5 as 1 of its child.
yes, I watched it and explanation is good but he didn't explain the inodersucc() function. And that is the only doubt I have otherwise here too mam explained quite well
for those who wonder why we are looking for curr->left in InOrder Successor
answer : if we look in curr->right then we will be looking for values that are > curr->data and if we look in curr->left we will get values < curr->data, and ofcourse we want to replace the parent node with a value less than the curr->data to preserve the BST property i.e (parent->left->data < parent->data < parent->right->data)
We understand in easy words we just find our inorder successor of the node has to be just little greater .
then how can we call it as successor...it would be predesor?
GOT THAT......SEE WHERE THE FN IS CALLED...THERE WE HAVE PASSED ROOT->RIGHT NOT ROOT.....AUR AB HUME ROOT KE LEFT KO TALASHNA HAI....
Code is not very good basically.
@@adityashubham6242 it will be successor for root (yeah ofcourse smallest value in given sub tree but greater than root)
anyone wondering why we are looking for curr->left, look before we are calling inorderSucc for root->right, means we are looking for all elements greater than root, and we want the least value thats greater than root, and thatll be present in the left most element of the subtree with node root->right
Same qs? 🤷
Thank u so so so much Team AD❤
Keep it Up
Hat's off to this Ma'am!! Best Explanation!! So much efforts by whole team!!
Nice mam
No one teach like you
Awesome 👍👍👍👍👍
Woh di very good explanation 👍🥰👍🥰✨✨❣️
AWESOME LECTURE HAI KEEP IT UP MAM
Thank you Ma'am, it really helped me.
Congratulation on 1 million subscribers 🥳🥳🥳🥳
Thank u very much didi❤
Thank you so much ma'am
In the first go i had not understood anything because I had not took pan paper with me. After 2 days somehow I came again and now i had pen and paper with me and broke problem in 4 sub problem and tried each individually as new question :
1.Delete a leaf node in bst
2. Delete node with one child
3. Delete node with two child
4. Find inorder successor of a node in bst
And now this problem seems very easy as compared to 1st time.
Conclusion: untill you don't use pen paper you can't able solve problems exception are there for super minded peoples.
I feel the same
Best explanation ever
Such a good explanation 😃
Thank you 🙏🙏
thanku Bhaiya ji andAC TEAM members :)
This is why Search in BST is depend on Height.
Consider BST as below :-
1
2
3
4
5
Here height is N so time complexity is O(N)
So Actual Time complexity of BST search: O(H)
Average case Time complexity: O( log N )
That is worst time complexity
1. Best case will be O(1), when we get element at roor itself
2. Average case will O(logn), when we search element in either left or right sub tree
3. Worst case will be O(n), when the BST have only one direction subtree in its child
That's why we use avl tree
excellent teaching and why haven't you added AVL trees concept?
Atta nahi hoga , tujhe kya be
Inhen avl tree aur binary tree me koi antar nhi dikhta isliye to sari time complexity avl tree k btaya he isme
This Man Is Going Crazy Keep It Up 😆 Thanks You So Much For All The Lectures❤️🙏
bhai pdh bhi rahe ho sath me ki ni
@@yashasvi9301 nahi abhi 12th khatam ho gayi he ab start karunga
good explanation
Wow what a leature😘
sure these videos are helpful, but for people having good experince with recursion. For a lot of people including me, we have a hard time understanding the logic of how and why exactly the code was written the way it is. It would be really great if you also give a line by line explanation plus line by line example to show how the code works, specifically the recursion part.
for those who wonder why we are looking for curr->left in InOrder Successor
ans: if we look from curr->left and curr->right both are similar to delete you can dry run the code by writing curr->right instead of curr->left ans will be same
For best delete explaination
Maja aa gya
Did anyone notice she said :"humein phele se pata hai time complexity of search in BST is o(n) thats is why we can say that time complexity in seacrh in BST is o(n)" ...kya ghumaya hai shabdo mei 😂😂😂 "great work"👍
😂😂
They said in case 3:we find inorder successor first then they code in case 3 they store min value in temp variable
6:50 if we put log both side then hlog2 = log(n+1) and in next step u wrote h = log(n+1) ,so where log2 gone?
What about "dangling pointer" after we free the memory???
in search the function should also have return null otherwise some compiler will give error
thanks bhaiya
Nice lecture
Please upload Notes as well !
Very convinient example you have right there, are you sure the code will run if the inorder successor has a left subtree?
If the inorder successor has a left subtree, it cannot be the inorder successor. Think about it...
Tanky
Which compiler u used
you will also write the code or and link of the code in description
By the Way, It's just Good
one liner for search
node * searchBST(node * temp , int key){
return (temp == NULL || temp->data == key ) ? temp : ((temp->data > key)? searchBST(temp->left , key) : searchBST(temp->right , key)) ;
}
hlo mam aap please list /array ko input kr ke baata sakte hoo means list nhi deni pehle
Does not deletes if only one node is present
thank you mam
@Apna College sir this code does not work if you want to delete the root node or if you pass any value that is not present in the tree(test case)
Keep Up
19:29
Vaiya notes???
Pehle k lecture 8.2 aur kuch kuch lectures mai notes nhi hai .
Please,vaiya notes vi dal dijiye.....
maine binary tree se start ki thi abhi tak ek bhi notes nhi mili
Plz koi iss ka code bata du
Write down a program to store values in binary search tree. Program
should keep taking values until we enter values less than 100. After
entering values, print all unique values in
What does it mean to free the root ?
free(root) ...?
But how does it explains the deletion of leaf nodes...no cases considered ig
If i try to delete each node one by one by perform delete function for all nodes and then if i print the inorder traversal still it prints the last element which i delete. Why??
Plz reply ....
Could not understand inorder successor concept. Bar bar left m kyu ja rhe h
curr-> curr.left
please elaborate the logic
"The successor will be the left most child of the right subtree or right child itself". Here in case 3 we are passing the argument [inorderSucc(root->right)] , hence we are going to the leftmost child of the right subtree. That's why we are progressing till curr->left != NULL.
P.S- We are going till the leftmost child of RIGHT subtree because it would be the element just after the curr node in "inorder" sequence
@@akshitahuja2602 it's progressing till curr && curr->left != Null
Won't it make the curr null??
@@rahul_ji21 no,if you check carefull we just need curr->left!=NULL because the next successor will always be a leaf node
@@piyushlohiya1977 thenkss🤗
To find just Max value after key in BST
I have a doubt, if the BST is flatten what will be the time complexity of searching in BST? O(n)?
bst cant be flatten ig, bc in flatten left subtree gonna be above the right subtree, and then that tree is not bst anymore.
@@tarunbisht8016 Consider BST as
1
2
3
4
5
What about base case in delete function when key not found in BST?
Extension name?
where are the notess???
notes nhi milenge kya
osm
Where are notes
❤️❤️❤️
what does the free method do?
please answer this: can we free(temp) instead of calling delete BST IN LINE NO. 56????? THink
Answer is NO! if inorder succ. happens to be a left child (at the right side of root offcourse)..if it has right child only...then passing the function remains only option.
python mai v tutorials dijiye
please
this is giving me an error, let's suppose a tree
5
/ \
3 10
/ \ /
2 4 9
/
8
so, when I'm deleting 9, 8 is also being deleted, and when I'm deleting 10, 9, and 8 are also being deleted, whereas, if I delete 3 or 5, they are displaying everything fine. IDK, if it's something with the code or just my personal error, as we're told that if we're deleting a node with 1 child, I'm supposed to relate, its parent to the child of the node being deleted. I don't see that happening. but as i said, it can be due to some sort of personal error, if someone can decode my problem. i'll be glad.
I am assuming when you delete 9, it is also dropping the nodes below it as the code has no connection to that node so it can't be searched.
what if the inorder sucessor have a left child
Like in this what happens if 4 have left child
Case 3 me
root-> right=deleteBST(root->right,temp->key);
Is line me doubt hai
It is temp->data not temp->key
we r doing that to delete the right node and reattach the rest of right branch
@@learningoverflow3138 what does temp->key means
What if binary tree has n level
NOTES ????
Guys can you send notes of trees topic
bst se gst yaad aa jata hai
Why ain't we using bool func for searchinBST function?
yea, you can use bool function also
bool is also possible, but then it will show only if the element is present or not, you can't do anything else sadly
Can anyone please tell me why are we returning Node* in the search? Can we not solve it by returning bool
Yes we can, apply bool and see the code working the same
I don't think so, because you'll be returning the child-node (if there is one) to the key's previous root's pointer.
I didn’t understand this root->left= deleteinbst(root->left,key)
when key is smaller than root->data, we have to go in root->left to find the key and then delete it. After deletion temp is returned which will be joined to root->left , therefore we are taking the return from deleteinbst(root->left,key) in root->left
Try to dry run the code for the below tree;
5
/ |
2 6
\
3
@@kumarivandana1554 okay, thankyou
what's temp->key?
it should be temp->data actually
Can anyone share the code...., I am getting error in inorderSuccessor (not declared in scope). Watched the lecture twice but still not able to debug it.
Node* inorderSuccessor(Node* root){
Node* curr=root;
while(curr->left!=NULL){
curr=curr->left;
}
return curr;
}
#include
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
Node(int val){
data=val;
left=NULL;
right=NULL;
}
};
void inorder(Node* root){
if(root==NULL){
return;
}
inorder(root->left);
coutleft;
}
return curr;
}
//Delete in BST
Node* deleteInBST(Node* root,int key){
//search the key
if(keydata){
root->left=deleteInBST(root->left,key);
}
else if(key>root->data){
root->right=deleteInBST(root->right,key);
}
//key is found
else{
if(root->left==NULL){
Node* temp=root->right;
free(root);
return temp;
}
else if(root->right==NULL){
Node* temp=root->left;
free(root);
return temp;
}
Node* temp=inorderSuccessor(root->right);
root->data=temp->data;
root->right=deleteInBST(root->right,temp->data);
}
return root;
}
int main(){
Node* root=new Node(8);
root->left=new Node(2);
root->left->left=new Node(1);
root->left->right=new Node(5);
root->left->right->left=new Node(3);
root->left->right->right=new Node(7);
root->right=new Node(9);
root->right->right=new Node(10);
/*
8
/ \
2 9
/ \ \
1 5 10
/ \
3 7
*/
inorder(root);
cout
@@rohanyadav7542 thanks rohan
sir please source code ka b link dia kre
u are saying successor...but it should be min value on the left side...copied from gfg at least use right terms..it was confusing
it works all good. But whenever i try to delete the last root node available in the tree with no child, am unable to perform anymore functions and the program just closes itself.. like for e.g after deleting all the nodes, i call the delete function again, instead of gettin message "tree is empty" my program just stops executing itself.
if anyone knows anything regarding this then let me know :) thanks
add if(root==NULL) in your code
Ig something is wrong with delete function
can somone explain free() function please
delete smjh nhi aaya :(
i didn't get the inordersucc function code part why loop will execute till curr and curr->left != NULL..WHY?
Bro here the code is wrong for inorder successor
bhai kyuki inorder sequence hamesha sorted order of elements dega aur left tak isliye jaana hai kyuki bst ke properties ke hisaab se left me hi hame chote values milenge aur inorder me bhi yahi hota hai.So not to break the rules of binary search trees
"The successor will be the left most child of the right subtree or right child itself". Here in case 3 we are passing the argument [inorderSucc(root->right)] , hence we are going to the leftmost child of the right subtree. That's why we are progressing till curr->left != NULL.
P.S- We are going till the leftmost child of RIGHT subtree because it would be the element just after the curr node in "inorder" sequence.
When God come to help poor students ❤️
Is programme handling the case where both child's are null
yes
@@fulcrum2277 Where?
@@anuragpandey3341 in the first condition of root->left==NULL because even if the right is NULL as well we will return root->right ie NULL
When will c language course start
bhai ye C language course hi chal rha hai...!!
@@ritikpratapsingh9128 bhai yee c++ ka cource he c ka nahi
@@anonymous.u.s.e.r bhai ek hi cheez haii....thode se change ke liye...pura course to release krenge nhi!!
@@ritikpratapsingh9128 bhai c or c++ me difference kya he yee kese pata chale ga
@@anonymous.u.s.e.r bhai koi difference nhi hai....jo tu c mei kr skta hai vo sab c++ mei kr skta hai...!! thoda bhot internal functioning mei farq hota hai...thoda bhot syntax mei....pr vhi cheez hai almost
Shouldn't the Time complexity of Search still be O(n)?
because the BST is not a balanced tree, so the max height can go up to n.
that is very rare case i guess thats why
@@tarunbisht8016 big O accounts for worst-case complexity and O(log n) is its best-case complexity.
@@shubhsahu4780 not the best case I guess best is o(1) if I'm searching the root note of a tree
@@tarunbisht8016 Oh sorry, my bad. But O(log n) is not worst-case complexity, it is the Average case.
@@shubhsahu4780 NO average case is o(logn) because in most of the cases we gonna have both left and right subtree but in the worst case, either left or right subtree will be NULL and the element I have to search will be the last node of that subtree
when a node has 2 children like 3 has 2 and 4 , 3's ancester is 1 , then can't 3 delete directly and make 2 and 4 children of 1
bro what about second child of 1 ? what if one already had 2 children for example 3 and 5, then if 3 is deleted we cant make 2 and 4 as children of 1 bcoz it already have 5 as 1 of its child.
bro what about second child of 1 ? what if 1 already had 2 children for example 3 and 5, then if 3 is deleted we cant make 2 and 4 as children of 1 bcoz it already have 5 as 1 of its child.
the code was so complicated and didn't run too.
bhai usne bhi yhi bola tha😑😑😑....it's complicated
free se error aa rha
mycodeschool on youtube has explained deleting of a node very well if u have any problem in understanding
check that
yes, I watched it and explanation is good but he didn't explain the inodersucc() function. And that is the only doubt I have otherwise here too mam explained quite well
@@adityabhandari6688 Watch Code Library's video on successor of bst, he explained it well
what is temp->key?
It should be temp.data
@@harpic949 okay thanks