DELETION OF AN ELEMENT FROM BINARY SEARCH TREE(BST) - DATA STRUCTURES

[Music] hello friends welcome back to our channel so in the previous session we have seen the introduction to binary search tree and how to create and how to insert an elements into the binary search tree so and also the different operations that we can perform on binary search tree so in this session we'll go with one more operation that is deletion so how to delete an element from the binary search tree and what's the procedure duration in by est est is binary search tree so just recall the property of binary search tree so it is a variance by directory that means every node should have an at most two two children and also consider the root node and all the elements which are less then the root node should be in the left subtree and all the elements which are greater than the root node must be at the right subtree and this should be followed in this also so by deleting an element from the binary search tree it should not violate the property of BST so even though you delete the element from the binary search tree the elements less than the root code should be in the left subtree and their elements greater than root node should be in the right subtree see so here we can delete an element in three cases so first case deleting an element or deleting and lower with no children so you know that it's a variant of binary tree every node will be having it most to two children at most two children means we can have zero one two every node will be having age of zero one or two children so deleting a node with no children [Music] deleting a node having one child deleting a node having two children so these are the three cases we can follow by deleting an element from the BST so here element or node with an equal right so let us see one by one so we have to delete an element from the phd so that that tree should not violate the property of BST let us consider the first thing deleting a node having no children that means leaf nodes leaf nodes so let us take an example so there will be no problem if you delete the elements of a leaf node right so that the property should do not violate the BST right so let us take an example so that you will be understand right right so let us say let us take this example so that first of all you construct the binary search tree and then we will delete the green treatments so first consider the hoop nor then 3 3 is less than 8 so it should be in the left subtree and greater than so right subtree gone less than so again 1 is less than 3 so left subtree of 3 6 less than 8 and greater than 3 so here it will be inserted footing greater than 8 is greater than 10 so right how high it said for less than 8 and a greater than 3 and in less than 6 7 less than 8 greater than 3 greater than 6 13 so greater than 8 right so greater than 10 less than 14 so this one is a protein this is the binary tree okay for this elements now delete the nodes which are having a no children so that means leaves nodes so here the leaves those are one so because it does not have any children Rama 13 comma 13 only two elements are there this one this one so deleting the elements or deleting the roads with no children doesn't effects the BST just remove the connection between this element and parent element and just to free this node so after deleting the elements we get 8 3 [Music] six four seven that's right so after deleting 113 right yes we have removed the connection between the leaf node and the pin right and here let us check the property of PST eight is a root node so that this subtree but completely left subtree should contain the elements which are less than e so 3 is less than 8 6 is less than 8 4 7 all these are the elements on less than 8 right next this is the right subtree so we know that all the elements of a right subtree should contain a greater than the root root for the 10 14 both elements are greater than 8 so it satisfies the BST even though deleting the leaf nodes 1 and 13 so there is no issues simply we can remove a connection and we can free the loop if it is a leaf node so that is the first thing we will go with the second thing so deleting a know what having one children that makes one chain one changer so let us take the same example same example see deleting in know what having one chain so we have to delete and node which is having only one chain so here eight is having two children three is having two children six is having two children and coming to this ten having only one children ten is having only one chain so single child nodes what is that n come on and forty does also have only one chain so 40 so we can delete the able stem and food beam so first let us delete the ten first let us delete the ten so simply simply if you build the ten the chain will becomes the chain will replace the position of the paint so if the chain the parent is having only one change the chain will replace the position of the pinion so here child will replace the position of a pain this is the only thing happens in deleting a node having one chain so after deleting an elements let us check the property of a BST now we'll hit the tell a mediating can after deleting ten see eight three one six four so then we are deleting the ten so what is the child of a 10 it's a 14 right we are deleting the element 10 so what's the change of fourteen so here the statement is change will really plays the position of a parent so 14 will replace the position of a 10 so 14 becomes the child of 8 because 10 is a child of 8 so 14 13 so let us check whether it violates be the property of BST so this is the left subtree so in the left subtree the elements are less than 8 so 3 so in this subtree again the evidence of left subtree should have the less than gu that means less than 3 less than I made greater than 3 so 6 4 7 Redmond and coming to the left subtree then either than foot greater than a so 14 and 13 are greater than the 8 and coming to this 14 the 13 is less than 40 so 13 is a left subtree of 50 right so it doesn't boil it's the property of BST it doesn't boil it's the property of BST even we do it in the element n so let us take a 14 let us delete the 14 from here see here we'll be right here waiting for you right because 14 is a Nord with only one chain so let us delay the 14 so if you observe here the 14 is having the chain 13 so the formal statement change means implies a position of your parents so 13 will be the position of 14 that it will be replaced with the position of putting see 8 3 1 6 4 & 7 and see that it will be replace it to the position of 14 so so after deleting the footage from this one okay from this one from this BST after dating the 10 we will get this one this way BST from this BST again if you delete it 14 we will get this one so hope you understood so again you can observe the property of be hasty so it is also it doesn't violate the property of BST even though we are deleting the 14 so this is how we can literally a node which is having only one chain right now two children so how to delete a node having two children see here we can we have to modify simple them so deleting a node with two children so here also we can replace the parent position with another node right another chain here also we can replace parent with children okay we can replace a parent with chain so in that the chain can be the child can be minimum element of right sub-tree or J can be maximum element of left sub-tree right two cases we can replace so here also if you are dealing a parent right so here we are deleting a parent which is having a two children so here we can replace a parent with a chain we can replace a parent with a chain one is from the left chain a left sub-tree one may be from the right subtree so anyone can consider so if you consider the left subtree the minimum or the maximum element from the left subtree should be replaced and if you consider the minimum of the right subtree the minimum element from the right subtree should be in place anyone should be happy but what booth okay the barrel can be replaced with the chain either from left subtree all right subtree based upon this condition now there sit here now so here what are the notes which are having a to children notes with two children so first one eight eight is a root node each they're having two children three is having the two children six is having a two children eight three six right so three elements are there we can delete the three eight events here in the third case so let us say consider one by one so let us consider the six let us consider the first of six let us delete this thing's so deleting the six sixty should be replaced with a chain from either left subtree or a right subtree so if you consider the left subtree the maximum element should be replaced see so here eight three ten one six four seven see if you've observed here if you observe here so yeah replacing the six with either left subtree right subtree so left subtree means maximum element so here only two elements we can replace either to four or seven so if you replace the phone we have to delete this element for right after replacing way how to delete this element so deleting this element means this is a leaf node so we can directly delete this right so this is one way how to delete a node the parent node will be replaced with the either left child or right chain so coming to the left chain we have to consider the maximum element again coming to the right chain we have to consider minimum payment so this we can apply all or you can go with this seven that pays replacing the chain with the element from right subtree so we can replace six with a further four or seven so even tilting the four six also the property of BST is not violated because all the images of the left subtree are less than eight all the elements of right subtree are greater than eight so coming to the three so if you delete the element three see deleting an element from I mean deleting the node thing so the position of three can be replaced with the child of left subtree all right simply so here consider the left subtree first case consider the left subtree so here it is node it doesn't have any children right so it will be directly replaced with so one thing is if you replace the three if you replace the parent tree with the left node that is one the trees like this this is also correct right so we can replace the parent with change from the left subtree all right simply if you consider left subtree we have to go with the maximum element so here the maximum element is only one one element is there so we can replace the parent with the that particular element so one is here and we can simply delete this node if not so one so the six is greater than one so it is on left side of the right side of the 1 and a 4 which is greater than 1 and less than 6 so 4 is also on the right subtree but left to 6 and 7 which is greater than 1 and 6 so 7 is placed it better than i mean greater so it should be placed at the right side right subtree so this also doesn't violate the property of my decision so if you write so second case if you want to replace the parent from the right children so right channel means this one right for this right subtree we have to replace the what is the a maximum element of right subtree 7 7 so my first minimum element of right century what's the minimum element of this rights are 3 4 4 so 4 can be replace it with this I mean 3 can be replaced with the 4 so if you replace this 3 with 4 and we have to simply delete this element this isn't normal again this is a leaf node so there will be no problem and while deleting also we have to follow the same procedure well whether it is having children are one Shalom not Putin so here for is having no children it's a leaf flu so there is a no change so we can simply disconnect the link and we can free the space so after deleting the three after deleting the three we have choosing the child from right sub-tree so we are choosing the minimum value so that is replace will be the pain right so so this is also correct it does not all it is also doesn't violates the BST right so for the less than elements are left right and greater than anything so on I'd say so hope you understood this one okay right now right so no let us delete an element 8 8 so if you want to delete an element 8 if you want to delete an element 8 so that can be done from the left sub-tree all the rights that they left us at 3 or like something coming to the left sub-tree coming to the left sub-tree we have to replace the element with a maximum value of left subtree so what's the maximum of left subtree 7 so 8 can be replaced with 7 so here 8 can be replaced with 70 so there are two nodes so I have to remove this 7 so there should not be in duplicates we have to do it in the center again follow the same procedure check whether the 7 is a leaf node or Road with one child or road with two chips and follow the same procedure so here it is a leaf node so simply we can remove the element so it doesn't wire itself properly BST properly because all the elements of left subtree are less than 7 so 3 is less than 1 7 1 is less than 7 less than 3 so it is a left subtree and 6 which is less than 700 is n 3 and a 4 which is less than 7 and greater than 3 and less than 6 right so 1014 in 13 no it doesn't violate the BST property so this is 1 so this is 1 well if you choose a chain from left to something right now we'll go with the right subtree so if you want to replace this position with the event from right subtree so we have to find the minimum element minimum element so what are the elements of right subtree and 14 and 13 and 14 and 13 so among these 10 14 what is the minimum element and so tan should be replaced by I mean 10 should be replaced to position of 8 so if you replace this 8 with 10 we have to delete this 10 volt right so in order to do this 10 volt see this again it's a node with one chain so what with one chain is simple we can replace the position of a parent with a chain what do you want change so we can replace the position of parent with that particular kid so 10 is replaced with 15 again for the way our dinner for me so for this rotary flow so 14 should be again folding this is also a node with a single element so 14 should be replaced with chain so here 13 right and how do you say different so simply we can remove the 30 simply we can remove the 30 so this is how we have to apply the deletion operation so after deleting the element so just deleting an element means replacing the parent position with a chain and after replacing the parent with chain and we have to remove that original position of that particular chain and off after also for removing the torsional position of the chain we have to follow the same procedure right don't get capsules and it was simple easy and hope you understood this one right so three ways we can delete the three ways we can delete an element from the BST one is a leaf nodes and node with one child and node with two chains right so if you are having any doubts regarding this deletion process so feel free to post your doubts in the comment section so that I will definitely try to clarify all your ducks and if you really understood my sessions right magicians share my sessions with your friends and don't forget to subscribe to our Channel thanks for watching thank you very much

Channel: Sundeep Saradhi Kanthety

Views: 27,718

Keywords: sundeep, saradhi, kanthety, data structures, lists, trees, primitive, non primitive, linear, non linear, linked lists, ds fundamentals, ds basics, nodes, interview, placements, parent, child, leaf node, sub tree, root node, tree terminology, TREES IN DATA STRUCTURES, binary trees, binary search trees, BST, BST BASICS, BST CONSTRUCTION, BST EXAMPLE, BST INTRODUCTION, binary search, insertion, construction, right subtree, left subtree, deletion, bst deletion

Id: -WUbbRxdbL8

Length: 28min 2sec (1682 seconds)

Published: Thu Jul 25 2019