Deletion of a Node in BST - Node having 2 Children | Mr.Srinivas

you hi everyone welcome to nourish technologies this is universe so in the last session we discussed how to delete a node with a single child in a binary search tree now in this session we are going to see how to delete a node how to delete a node is having two children in a binary search tree deletion of node in a binary search tree and here the concept is node having two children is a heading how and here also so many possibilities are there possibilities so what are the possibilities already we discussed right in a previous sessions very clearly if you want to delete a node is having two children some of the nodes I am taking some of the nodes suppose 50 60 70 80 65 55 53 57 40 30 I have inserted some of the nodes by following the rules of a binary search tree by following the rules of binary search tree here whenever we are inserting the elements whenever we are inserting the elements so we are following the rules nothing but the so greater values moved to right side lesser values moved to left side but now I just want to delete this one this is my target I want to delete this node a node is having two children left children is there and right child is there then after deleting this node with which node we have to replace so that is so whatever the highest element in the left subtree this is left sub-tree this is one highest element highest element in a left subtree and next one what is the least element in a right subtree so what is the least element in the like right subtree that is a 65 least element in a right subtree two options you have nothing but 16 node you have to replace with either 57 or you can replace with 65 so then only we can satisfy the rules of a binary search tree after deletion of a node is having two children okay and how to delete and so many possibilities are there we'll see one by one see for example so I am taking so one pattern one tree we are taking some of the nodes is having some writing the nodes 50 suppose 40 60 70 80 and here it is 55 node addresses also thousand 2,000 3,000 4,000 5,000 and 6,000 here it is a left child is this here it is a right child is there X here also left child is present right child is present next here it is a right child is present and remaining nodes are null nodes so possibilities now this is a target node is nothing but this is the current node and this is the parent node consider this is the current node and this is the parent node now possibilities right so what are the possibilities so current sir after deleting this 60 so what approach you will follow highest element in the left subtree or a least element in the right subtree i will go for least element least element in a right subtree I will replace with a least element in the right subtree after deleting so this is a right subtree this is a right subtree so what is the least element in the right subtree is a 70 only 70 sorry that means here it is the node is a current now we need to check one more thing how you can confirm that this is having two nodes means if if current to left not equals to null and current to write not equals to null current to left not equals to null current to right not equals to null so then only it is confirmed that the node is having two children if current to left equals to null current to right equals to null means what is node having no children is easy for D to delete and current to left not equal to null right equals to null or current to left equals to null right not equals to null that is node is having a single children that is also we discussed very clearly in a last session now left children is not empty and right children is also not empty so node is having two children but now in this case right if we should go for right subtree a least element so we are taking one element struct node struct node star suppose T 1 comma T 2 two pointers into T 1 into T 1 so we are taking the current to current to right current to right we are taking current to right this is for example if T 1 2 left equals to null serve wiser reason suppose if left not equals to null suppose here it is 1 node is there imagine so what the node will be is less than 17 greater than 60 less than 70 for example 65 by that time you have to delete with this node or for example T 2 left child is not there and right child is also not there very happy you just want to delete this node whenever you want to delete this node whenever you want to delete this node what you have to do means we need - gopher right sub-tree list element but in a right subtree only one node is there 70 so that is what we called a t1 current to write equals 2t 1 this is pointing by e1 e1 value five thousand current value three thousand three thousand e one value is a five thousand now we are checking even two left equals to null you want to write equal to null if e1 to left equals to null and II want to write equals to null null so very simple just a one data store into current data even data is what 70e one data store into current data 70 we are storing nothing but 60 60 is replaced with the value 70 is replaced now we are deleting this node because anyway no nodes are present how to delete this node means here there is no right pointer here it is a five thousand we should make it null five thousand we should make it null right how current to write equals to null after this into current - right we are storing null value simply free of e1 free of a1 because T one is pointing to five thousand no pointer then you can call a free function on this this is one approach second approach for example it is having the node it is having the node just look at this now so I'm writing the notes for example here the value 60 and next one here it is a some value is there like a 55 and here it is a value 70 here it is a value eighty three thousand four thousand it is null it is null four thousand here and next one five thousand is here and suppose six thousand is here and the remaining nodes are null now as usual this is a parent this is current now so current to write as usual we are storing into t1 nothing but current is a 3000 and X 1 T 1 means what current to write this is a t1 current or 5,000 now we need to find out the least element in the right subtree least element in the right subtree so then in this situation what we have to do means current to left not equals to null current to right not equals to null is okay but next at t1 e1 equals to current to right and simply now we are checking if e1 to right not equals to null you want to write not equals to null and p12 left equals to null even means what is a 5,000 5,000 to left equals to null and x1 you want to write a not equals to null not equals to null then what we have to do so very simple here it is pointing to 5,000 all right so now observe two things first you need to delete this node deleting nothing but 70 we are placing here 70 we are placing here how to place a 1 a 1 2 data will be stored into current to data II 1 2 data will be stored into current to data nothing but 70 will be stored here X in the previous case before deleting this one here we are writing null now before deleting this one here you have to place this node value this node is what a 6000 how to place p1 to write is a 6000 a 1 2 right a one-two right so we'll be stored in two current to write a 1/2 right will be stored into current to write t1 2 right is a six thousand that we are storing here is a equals to current to right six thousand then it stopped pointing it start pointing to this one now we need to delete this node before deleting this node here you have to place a null value because it is connecting we need to destroy this connection how you want to write equals to null e 1 2 right equals to null and finally free of e1 this is ok that is nothing but before deleting the node in the right subtree right that right child is having any animal another right child then you will face problems after deleting this node directly you cannot delete by placing null here because we lost some other connections also that is why first we have to connect this and then separately we need to delete this one this is and one more thing is there suppose if it is having left children then problem we should move all the way down to find out the least element and then we perform deletion operation right how to perform deletion operation that we'll see in a next session for more videos so please subscribe to nourish 80 channel thank you

Channel: Naresh i Technologies

Views: 73,326

Keywords: Data Structures, Srinivas, Naresh IT, Hands on Data Structures Training, Learn Data Structures, Data Structures Demo, Online Data Structures Training, Data Structures Tutorial Videos, Data Structures Overview, Data Structures Interview Questions

Id: lsGRy7DUcNU

Length: 15min 13sec (913 seconds)

Published: Fri Oct 21 2016