Delete a node from Binary Search Tree

See complete series on data structures here:
• Data structures
In this lesson, we have discussed deletion of a node from binary search tree data structure. We have discussed the core logic and written implementation of it in C++.
See source code here:
gist.github.co...
For practice problems and more, visit: www.mycodeschoo...
Like us on Facebook: / mycodeschool
Follow us on twitter: / mycodeschool

[@phew...6097]

Who's watching in 2024? :D

[@muralikrishna.ruttala5546]

It's me

[@Mr.Aziz.753]

Me 🙋

[@lv3234]

me

[@iamparitosh]

The number of lives this channel has touched is far far greater :) Reason: In the year 2014 there were hardly any DSA channels on youtube This very channel inspired the entire generation of Data-Structures KZbin Channel.

[@pranatinayak1463]

I have starting liking data structures after going through your videos.. Really appreciate !!!

[@lindawisebear]

"Woohoo I found you, get ready to be deleted" 😂😂😂

[@devprakash5320]

Bazingaaaa

[@aakashyadav6228]

@@devprakash5320 huhh..Sheldon

[@kunalsoni7681]

😂😂😂😂😂

[@iamparitosh]

XD

[@hacksbsb]

the op is dead

[@afrozanjum5086]

Out of all the search results KZbin shows me when I search a specific topic I always look for mycodeschool Videos. Simply outstanding!

[@TehFingergunz]

best explanation on youtube in my opinion, this helped me when I took data structures and algorithms and it helped me again when I went to tutor it a year later. Well done and thank you.

[@akhilrajnambiar2080]

A headache concept(for me), explained in the most simple way! Pure brilliance.

[@swatiagrawal5385]

excellent explanation of deleting element from BST. Thanks.

[@ramyaradhakrishnan7881]

Really a good explanation of BST.Worth watching to this tutorial.Neatly explained.Thank you so much.

[@RandomSerialKiller]

Even in 2021 when there are so many videos/playlists available on KZbin, it's hard to find this much easily understandable and quality content on DSA. 😍

[@yashpatidar.8506]

i agere

[@Shourya_performs]

100% agreed

[@vengalrao5772]

2022

[@CuriousAnonDev]

I completed the playlist Can you please recommend resources for studying next concepts like graph algos, dp, etc?

[@julurisaiteja8853]

@@CuriousAnonDev Unfortunately one of the two people who started this channel is no more.He died in an accident in US and the other person wasnt in right state of mind for few days.I hope they r both fine in their own worlds now ....lots of love to their work

[@amellperalta]

Great explanation! Thank you. By the way, I'd like to point out that this deletion algorithm is not suitable for balanced trees since it will not preserve the balance. This algorithm is called Hibbard deletion, and one company was sued in the past for implementing this algorithm as the deletion method in a Red/Black tree implementation.

[@stormshadow76]

This is only for binary search tree .. it won't work for AVL trees and Red Black trees

[@happinin]

i had a lot of trouble understanding this! thank you so much! clear as hell explanation where all other lecturers failed. clear and simple and to the point! you are awesome my friend awesome!

[@nikkygeorgephilip5242]

Your lectures are awesome,easy to understand and practise. Thanks for your effort.

[@jakeharding8528]

Thanks for the video. Question on case 3, if there are two 17's on the right side, the tree would become invalid because you would have a value that is

[@CodeMalek]

14:22 "i hope this is making sense" my brain : farting

[@kaus05]

Glad i am not the only one lmao

[@burabazt1307]

@@kaus05 bro this shit just making my head like its gonna explosive

[@hruturajkedar2736]

Best KZbin channel on dsa

[@AfhamAdian]

this is the best content you can find to exist

[@t5a55i]

4th video I am looking at, very good and clearly explained. Thank you for your effort! Had to recapitulate for an interview, ages since I learnt it in school and had to use it.

[@tangudusaikiran5893]

I directly started trees ds,and i really loveing it because of you buddy

[@jeffisded1222]

Thanks! Your explanation was easy to follow

[@pfever]

I have followed all your Data Structures videos, they are great! I love that you just dont explain the ADT but also show how to code it. That´s really helpful for somebody like me which still doesn't have lots of experience coding. Keep the good work! I'm waiting for your new videos to come out! =)

[@waiuphigh]

amazing how my college professors don't take the time out to explain it in depth as much as you do, truly appreciate it.

[@vikranttyagiRN]

because they themeselves don't understand it in depth. what a sorry state

[@kannanhassouna5706]

i believe, in some case that we don't pay that attention in the lectures

[@conradmbugua9098]

@@kannanhassouna5706 Or the lecturers are too boring and don't make the lessons interesting, at the end of the day we are humans and operate on emotions

[@joshuadgoldberg1176]

great video, your English is very clear.

[@musyllabus8401]

thank you so much....i think this was the best video of programming language i have ever seen....keep it up...and thanks....your quality of explaining the concept is really very good...

[@newoap]

Fantastic video. Your description helped me to understand tree deletion. Thanks.

[@RajSehmi5293]

You are the best. Just Best. You made it so easy. Salute you. You are the Best Teacher

[@shubhamthind8286]

Best video on BST deletion.

[@dipeshbudhiraja8557]

//Function to find minimum in a tree. Node* FindMin(Node* root) { while(root->left != NULL) root = root->left; return root; }

[@kartikxramesh]

correct

[@NEERAJKUMAR-db9se]

but we are interested in finding maximum in left subtree or minimum in right subtree..and you are showing the overall minimum for an entire tree...

[@nikolastevic2278]

@@NEERAJKUMAR-db9se Every subtree is also a binary search tree

[@sudeshchaudhary4558]

@@NEERAJKUMAR-db9se for function FindMin() Node* root is variable. We can use it for the right subtree as well.

[@alterguy4327]

return root->data

[@ankitmathur1962]

Your lectures r awsm..bt plz increase ur speed of uploading new videos....we r eagerly waiting for more lectures in this series...plz be fast

[@mycodeschool]

ankit mathur - We are also trying to figure out how to speed up. :P We focus on quality and its not so easy to speed up with quality. But we will try our best and publish videos more frequently. :)

[@ScrappyVids]

people are hungry for knowledge :p

[@Toopa88]

ankit mathur I hope he will upload a spelling video too.

[@bama2619]

you are great! I am watching your video from school 42! Thank you.

[@sagarikakadambi3720]

I cannot say enough how helpful these videos are. You are literally saving my grade, one video at a time. Thanks for being an amazing teacher, these videos are the BEST.

[@rayaankhan787]

you could have said these videos are the BeST ;)

[@dhakad22klx]

😂@@rayaankhan787

[@MinecraftLetstime]

This dude is a born legend.

[@SumitKumar-ww7he]

This dude is no more😭. God took him to teach binary tree.

[@irfashaw1989]

Wow it's amazing tutorial and good channel. For many problems related to coding and dry run I get solution from here.keep it going 👌

[@shahreazneeloy2119]

Boss....why struct node* temp = findMin(root->right); it should be int temp = findMin(root->right); root->data = temp; root->right = deleteData(root->right, temp); Many many thanks for your videos.....you are a greate teacher..:)

[@VermaAman]

because that function will return the NODE with minimum value(i.e., it'll have data, left and right).

[@chems_sed990]

The best course ever thaaaaank youuuuuu so much 🙏🙏🙏🙏

[@BhanuPrathap]

That minimum value in general case(in case of characters or any other data ) is inorder successor

[@pranavkotteswaran4093]

After deleting a node with two sub trees, we can connect parent of the deleted node with left sub tree of the deleted node . Also we need one more connection. We need to connect right most node of the left sub tree of the deleted node with the right sub tree of the deleted node . This approach would be way simpler than the approach mentioned in the video. BST property will always be conserved.

[@gauravbharti5390]

Really nice ! Its clearing my concepts !! Its simple and to the point.

[@brandm5176]

if you want to update then root->right=function() or else just function(). Here you need to update each and every process. And get the upmost root.

[@bhuwanmalik2034]

Nice collection of data

[@sanjitpaul2953]

Great Sir. Very lucid explanation.

[@sayakmandal4384]

Your explanation was so good..I understood everything..but I have a question if the node 7 had only a left child..let's say node 4 and we want to delete node 7 then what to do ??? if we make node 4 the right child of node 5 (the parent of node 7)..doesn't that violates the property of Binary search tree????please answer anyone...lots of thanks..🙏🙏

[@coding953]

If Node 7's parent is node 5, then Node 7 can't have a childe of Node 4, because all the value on the right of node 5 should be greater than ndoe 5.

[@chloekimball536]

This is amazing. Do tutorials on AVL trees, B Tress and hash tables. Please, pretty please?

[@adityaatri2053]

@@amitdutta5610 Harsha SuryaNarayana , one of the best coder that India has ever produced.

[@shivammehta8284]

@@adityaatri2053 the humblefool

[@shamanthakrishnakg1978]

He is not alive .

[@Amitsa299]

@@adityaatri2053 he is not Harsha, the video maker is Aminesh he left making a video anymore since his partner died in accident and Animesh joined Google, therefore no time.

[@rohankumar-of5qe]

Brother unfortunately he is no more..!!

[@harini3191]

sir, your videos are really good and thanks for your efforts. Please make more videos for graphs!!

[@how2tech403]

The person who made these videos is no more :-( ........RIP HUMBLE FOOL

[@harryxu7132]

Best explanation!!!

[@lucygaming9726]

Beautiful application of recursion.

[@thecuriousone12]

I had a hard time understanding the deletion process from BST, especially the third case, when a node we want to delete has both of its children. This video has made me understand, you explained very clearly, and I came to realize that the procedure is actually quite simple haha. Thank you very much! Your channel is my favorite when it comes to algorithm tutorials! Please keep posting more, I really enjoy them!

[@molyoxide8358]

Same Here Right now for me.

[@waleedosama1630]

massive like ... i hope you keep on explainig everything in computer engineering :)

[@moomenaldahdouh]

for (i=0 ; i < inf ; i++){ System.out.println(" Thank you "); }

[@qR7pK9sJ2t]

This will not compile...Rather it will give an error... class name not declared.. no main function.. data type of "i" unknown.. "inf" is unknown..

[@geoffl]

those rare moments when things just click :) This explanation is excellent for me

[@tenzing323]

Code for BST in C is below. #include #include #define TRUE 1 #define FALSE 0 struct Node { char data; struct Node* left; struct Node* right; }; struct Queue { struct Node* bst; struct Queue* next; }; struct Queue* head; struct Node* root; struct Queue* Enque(struct Node* root) { struct Queue* temp1; temp1 = (struct Queue*) malloc(sizeof(struct Queue)); temp1->bst = root; temp1->next = NULL; if(head==NULL) head = temp1; struct Queue* temp2; temp2 = head; while(temp2->next != NULL) temp2 = temp2->next; temp2->next = temp1; temp1->next = NULL; return head; } struct Node* Front() { return head->bst; } Deque() { struct Queue* temp1; temp1 = head; head = temp1->next; free(temp1); } Empty() { if(head == NULL) return 1; else return 0; } struct Node* GetNew(char c) { struct Node* New = (struct Node*) malloc(sizeof(struct Node)); New->data = c; New->left = New->right = NULL; return New; } struct Node* Insert(struct Node* root, char c) { if(root==NULL) { root = GetNew(c); return root; } else if(c data) { root->left = Insert(root->left, c); return root; } else { root->right = Insert(root->right, c); return root; } } int Search(struct Node* root, char c) { if(root == NULL) return FALSE; else if(root->data == c) return TRUE; else if(cdata) return Search(root->left, c); else return Search(root->right, c); } char Least(struct Node* root) { while(root->left != NULL) root = root->left; return root->data; } char Highest(struct Node* root) { while(root->right != NULL) root = root->right; return root->data; } int max(int a, int b) { if(a>b) return a; else return b; } int Height(struct Node* root) { int LH = 0, RH = 0; if(root == NULL) return -1; LH = LH + Height(root->left); RH = RH + Height(root->right); return max(LH, RH) + 1; } Level(struct Node* root) { if(root==NULL) { printf("Tree is empty. "); return; } struct Node* temp; struct Queue* head = NULL; Enque(root); while(!Empty()) { temp = Front(); Deque(); printf("%c\t", temp->data); if(temp->left != NULL) Enque(temp->left); if(temp->right != NULL) Enque(temp->right); } } Preorder(struct Node* root) { if(root == NULL) return; printf("%c\t", root->data); Preorder(root->left); Preorder(root->right); } Inorder(struct Node* root) { if(root==NULL) return; Inorder(root->left); printf("%c\t", root->data); Inorder(root->right); } Postorder(struct Node* root) { if(root==NULL) return; Postorder(root->left); Postorder(root->right); printf("%c\t", root->data); } struct Node* Findmin(struct Node* root1) { if(root1==NULL) return root1; while(root1->left != NULL) root1 = root1->left; return root1; } struct Node* Delete(struct Node* root, char d) { if(root==NULL) return root; else if(ddata) root->left = Delete(root->left, d); else if(d>root->data) root->right = Delete(root->right, d); else { if((root->left==NULL) && (root->right==NULL)) { free(root); root= NULL; } else if(root->left == NULL) { struct Node* temp = root; root = root->right; free(temp); temp = NULL; } else if(root->right==NULL) { struct Node* temp1 = root; root = root->left; free(temp1); temp1 = NULL; } else { struct Node* temp2 = Findmin(root->right); root->data = temp2->data; root->right = Delete(root->right, temp2->data); } } return root; } main() { root = NULL; char ch, L, H, ch1; int HT; HT = Height(root); printf("Before adding data the height of the tree is: %d ", HT); root = Insert(root, 'L'); root = Insert(root, 'F'); root = Insert(root, 'P'); root = Insert(root, 'S'); root = Insert(root, 'O'); root = Insert(root, 'E'); root = Insert(root, 'B'); root = Insert(root, 'A'); root = Insert(root, 'M'); root = Insert(root, 'R'); root = Insert(root, 'Y'); root = Insert(root, 'V'); root = Insert(root, 'D'); root = Insert(root, 'H'); root = Insert(root, 'J'); root = Insert(root, 'S'); root = Insert(root, 'Q'); root = Insert(root, 'W'); L = Least(root); H = Highest(root); printf("The least character is: %c ", L); printf("The highest character is: %c ", H); HT = Height(root); printf("After adding data the height of the tree is: %d ", HT); printf("The level order travarsal of the tree is. "); Level(root); putchar(10); printf("The Preorder travarsal of the tree is. "); Preorder(root); putchar(10); printf("The Inorder travarsal of the tree is. "); Inorder(root); putchar(10); printf("The postorder travarsal of the tree is. "); Postorder(root); putchar(10); printf("Enter the item to be searched and deleted. "); scanf("%c", &ch); if(Search(root, ch)) printf("Data found. "); else printf("Data not found. "); printf("Enter the data to be deleted. "); scanf(" %c", &ch1); if(Search(root, ch1)) root = Delete(root, ch1); else { printf("Data to be deleted is not found. "); return 0; } putchar(10); putchar(10); putchar(10); printf("After deletion of the data the new tree structure is: ,"); L = Least(root); H = Highest(root); printf("The least character is: %c ", L); printf("The highest character is: %c ", H); HT = Height(root); printf("After adding data the height of the tree is: %d ", HT); printf("The level order travarsal of the tree is. "); Level(root); putchar(10); printf("The Preorder travarsal of the tree is. "); Preorder(root); putchar(10); printf("The Inorder travarsal of the tree is. "); Inorder(root); putchar(10); printf("The postorder travarsal of the tree is. "); Postorder(root); putchar(10); return 0; }

[@Postsharing]

Watching one hour ago from paper 😂😂

[@innoirvinge8431]

Wow, this video is awesome! I was stuck with the delete function and couldnt figure out how to link the current ptr with its parent node :o, I did see a lot of sample codes and didnt understand how the recursion unfolds and sure enough I was missing that return statement :( I initially had my delete function to be void, now I understand what the return is for. Thank you so much, will definitely be watching more of your videos

[@pavittarkumarazad3259]

Never stop making videos! You are awesome :)

[@sanashahin7971]

In other words...If the node have two child then it should be replaced by the INORDER succession after the deletion

[@BelegaerTheGreat]

You are a proof that not every indian accent video is a bad video.

[@hangchen6131]

Best BST delete video on youtube... or probably across the internet, at all time.

[@maheshvangala8472]

Excellent explaination

[@anuragphadnis7806]

I took the baby steps of programming (DSA) from this channel and after 7 years I am here again for my interview preparation. Only if the channel was continued we would have seen the golden content. But destiny had some other plans. :(

[@1gouravgg]

and there goes one more excellent video..

[@mersihaceranic6762]

Thank you so much. The best one so far!

[@jamescheng6922]

I usually don't leave any comments, but this was very clear and helpful!! Thank you so much

[@itschax9102]

A Doubt again.... in case you are deleting a node with a single child, how are you establishing a link between the parent of that node to the left || right child of that node? (I mean the algorithm isn't explaining that)

[@asmitanand7951]

Thank you so much for awesome tutorials.

[@subhajitadhikary155]

Explained clearly thankyou

[@duncancamilleri8614]

hey bro very well explained - thank you kind sir!

[@aritraganguly3957]

Best explanation

[@richardjean-baptiste5170]

Thank you for your video, it helped me so much!

[@Sumit-wv7xk]

Hi, How are you making sure that once the node to be is deleted is deleted and the link to its parent is still maintained now between the child of the node deleted and its parent ? More specifically, else if(root->left == NULL) { struct Node *temp = root; root = root->right; delete temp; } After deleting the temp, what about the link between temp's parent and current root ? I am little confused here. Please explain if I am wrong. Thanks,

[@devavratabalvally2045]

root = root->right sets the pointer to a node we want. In the same iteration root is returned to the previous call of Delete. Here root->right = the returned root address. This will create the new link

[@SimKieu]

+Sumit Vohra root = root->right; just set a variable root pointing to root->right, so it wont create any new link. Your right. I dont think the code will work.

[@SimKieu]

+Sumit Vohra I dont even understand why he created temp then delete it, what's the point of creating it and not using it at all?

[@hypnocrabb]

If anyone is still wondering about this, look at the START of the code, where the right = delete. It will all make sense then.

[@shethnisarg3049]

he is just creating temp to free the memory, if he doesn't take temp then there will no reference to that memory and then you won't be able to free it.

[@nathanhazout7316]

Do any of the videos cover how to keep the BST balanced?

[@manjeetphogat6088]

case 3: //2 children root->right=Delete(root->right,temp->data) what we are storing in root->right??

[@manjeetphogat6088]

what Delete is going to return

[@manikantaneerugatti5206]

After every Delete call it returns NULL.

[@ElectorNiklas]

@@manikantaneerugatti5206 after every Delete call it returns root

[@parasbabbar]

There is another issue with the code, in your example you've been deleting elements from the right sub tree, if you try to delete from left subtree, your FindMin function will fail. def minValue(node, data): current = node if (data < node.data): # loop down to find the right most leaf while(current.right is not None): current = current.right elif (data > node.data): # loop down to find the left most leaf while(current.left is not None): current = current.left return current.data This is what I did to fix it.

[@sunshineinwilderness]

Thank you! its so clear now...

[@sourabhsingh4058]

what if 17 have 2 children (left and right) in the 3rd case

[@vigneshwarm]

exactly my thought.

[@ucvinguyen3333]

Thank you, I'm a Vietnamese. Somehow, I won't understand what ever my people talk about this. :")))

[@a3f35522]

Thank you, This was very useful for me!

[@clintonahong]

please upload the video of hashing,avl trees ,graphs.i have been watcing your series and it helps me alot in clearing the most difficulty parts.

[@giteshkhanna2633]

Nice explanation!

[@evgenyland4448]

thanks a lot, very cool and very simple

[@omarpolania]

Great video! really clear!

[@baraahekal8441]

Excellent explanation! However, I have a concern regarding case 3. By copying the child node's data to the current node, we lose the original address of the child node. I believe that when deleting a node, we should completely remove the node, including its address and data, and replace it with the child node, which has its own actual address that created with.

[@Soban.A]

In the third case, we pass the value of 'temp' into the 'delete' function as (root->right, root->value). This means that the 'delete' function will only work for the right subtree of the root, which will ultimately lead to case 1. This is because, when we find the minimum value, we are essentially finding the leaf node that is to be replaced.

[@NiteshKumar-xm3nq]

someone please continue this series , after the death of the owner no one is there to complete this series in the way he is continuing and i do not think any other can teach coding like this.

[@KshitijSharmaMe]

What if in case of a single child the child is the left node, for example thecurrent node 9 can be a left child of 7 as well. It can be something like node with value less than 5.

[@saisrisai9649]

Can never thank u enough! Thank uuuuuuuuuu

[@arielfuxman8868]

Thanks Man ! I loved it.

[@goyaldeekshant]

HERE IS THE COMPLETE CODE: /* Delete node in a binary search tree of integers Node is defined as struct Node { int data; struct Node* left; struct Node* right; } */ Node* FindMax(Node*); Node* DeleteNodeInBST(Node* root,int data) { if(root==NULL) { return root; } else if(data < root->data) { root->left = DeleteNodeInBST(root->left, data); } else if(data > root->data) { root->right = DeleteNodeInBST(root->right, data); } else { //case 1: No Child if(root->left == NULL && root->right ==NULL) { delete root; root = NULL; } //case 2: one child else if(root->left == NULL) { struct Node* temp = root; root = root->right; delete temp; } else if(root->right==NULL) { struct Node * temp = root; root=root->right; delete temp; } //case 3: two children else { struct Node * temp = FindMax(root->right); root->data = temp->data; root->right = DeleteNodeInBST(root->right, temp->data); } } return root; // Complete this function only // Do not write main method } Node* FindMax(Node* root) { if(root == NULL) { return root; } else if(root->right ==NULL) { return root; } return FindMax(root->right); }

[@TheRohit901]

Really sorry to know that co founder harsha is no more. Really appreciate whatever you guys have done for us

[@vitaminato]

Good job ! clearly explained. There is just one remark about case 3 :In your example, you assume that the minimum Y is the right child of the deleted node Z, which is not always the exact : It could be somewhere else in Z's right subtree which have no left child (of course) but has a right subtree. In this case, if you just copy the node Y into node Z, and after that delete node Y : this won't work i think, because Y's right subtree will be lost.

[@s98ks22]

I think you are right. When the node to be deleted finds the minimum in the right subtree, we need to verify if the parent of the right minimum is same as the node to be deleted. If yes, we do the same as what the instructor in this video said, otherwise we need to find the parent of the right minimum and set the left reference to NULL. I wrote this in Python like this (for the case with 2 children). I know I am answering 7 years later! 🙃 found = self.get_node(val) parent = self.get_node(val, True) right_minimum = BST(found.right).get_minimum() parent_right_minimum = self.get_node(right_minimum.val, need_parent=True) found.val = right_minimum.val if found is parent_right_minimum: parent_right_minimum.right = None else: parent_right_minimum.left = None In my case, I wrote a get_node function to find a node in the BST with the value needed. I also have an optional parameter in that method that gets me the parent of the node with the value I was looking for.

[@iqnolouser]

what if 17 has 2 nodes, examplef 16 and 20 ??

[@vandanasharma.sharma33]

awsm explanation..keep helpinggg...pls...!!

[@Joymyhome]

Very well explained! Thank you! I have a question. So since deleting max from right subtree and min from left subtree both make deletion work(for the case when a node with 2 children), which subtree do we choose?

[@roshanbadgujar4146]

massive like.Amazing work🙌

[@sergiojimenez3445]

Thanks for the videos, would have been good if I discovered this videos at the beginning of my education

[@alexrider1105]

this method is so much better than the method suggested in my "introduction to algorithms" textbook. Much easier to understand, and the code is cleaner. Great job!

[@13renschi]

Well explained!

[@nr.bln.]

best explaination I've found for this.

[@NiteshKumar-xm3nq]

i do not think there exist any channel which is comparable to "my code school" , this guy explains the code in the most easy and logical way while others do spoon feeding .

[@BhagatBikash]

After looking through so many resources, I must say that your explanation is indeed the best one on this topic. Really easy to follow and understand. Thank you !

[@sahin5051]

very very helpful. thank you

[@shishirgupta5978]

Thanks to you; now I'm more confused 😕