Binary Tree Part 2 | BST | Binary Search Tree - Data Structures & Algorithms Tutorials In Python #11

Key Takeaways

this is part two of binary search tree tutorial if you have not seen part one then please go watch that first in this video we are going to look at how to delete a node from a binary search tree as usual we'll go over some theory first then we'll write code in Python and in the end we'll have an interesting exercise for you to solve when you want to delete a node from a binary tree there are three different cases you might have the first case is let's see you are deleting a node with no child which is a leaf node basically so let's say you're building 9 here the delete operation here is pretty simple you remove the 9 from the right child of this node 4 and you get this ok this is pretty straight straightforward second case is let's say you're deleting 23 which is a node with only one child here you can just remove it and you can move 34 here at the top so your result will look something like this the most tricky case is deleting a node with two children here when you delete 20 after deletion you have to rebalance your tree in a way that the basic properties of binary search tree hold true what are the basic properties of binary search tree well all the elements should be unique for given node the elements in the left subtree should have a value less than the current node value and all the elements in the right subtree should have a value greater than the current value so you have to be very careful when you try to delete a node like 20 here one approach you can take is you can look into your right subtree here okay so what is my right subtree 23 and 34 and then find a minimum value from this right subtree and copy that minimum value here so you see I copied 23 here because my right subtree is 23 and 34 minimum of that is 23 so I copied 20 three here and once I copy that I can just remove the duplicates so 23-3 was duplicate so I removed it now why do we take minimum value from the right subtree well if you take minimum value from the right subtree and move here you are guaranteeing that all the elements which are left in the right subtree now are going to be greater than this root node or the base node just think about it all the elements on the right subtree are still going to be greater than this node if this node was a minimum of a right subtree that is the reason we choose minimum value and then we delete the duplicate node there is an alternate approach you can also look into left subtree so here just for the explanation cup purpose I added couple of more nodes but let's again same scenario okay you are trying to delete 20 which is a node with two children the first approach was find minimum from right subtree and copy that element the second approach is find maximum from the left subtree okay what is my left subtree eighteen thirteen nineteen what is maximum nineteen so now you copy nineteen here and after that you delete nineteen now why did we take maximum value if you take maximum value from the left subtree and put it here you're guaranteeing that all the leftover elements in the left subtree are still less than this value they will be less than this value because this was before a maximum of all the values in the left subtree all right so that's the theory now let's write Python code for the same this is the binary search tree node class that we implemented in part one and here we are going to implement this delete function where you can supply a particular value and it will delete nor from a binary tree now I give you an exercise of implementing finding max and finding min function in the previous tutorial so I hope you guys have done that exercise and implemented these functions on your own but if you did not then let me explain what these two functions are doing these two functions will just find you a maximum and minimum element from a binary tree now how can you find maximum and minimum well it's pretty straightforward when you have a tree like this the minimum element is actually you to just keep on going left and left the left most leaf node that you have is a minimum node so here number one is your minimum node okay and what is my maximum node well the maximum node would be you keep on going right hand side the rightmost leaf node that you have is a maximum node so 34 here is maximum so to implement min and max what you need to do is just keep on going left or right so here for max you can recursively keep on going right and if right is none which means you have reached the rightmost leaf node then you return that value otherwise simply do a recursive call and keep going one level down so here I am itself and when I do self dot right I am going one level down okay minimum is also similar so once you have fine min and fine max function let's now write code for delete so the first thing you need to do is you need to check if the value is less than cell or data okay if the value is less than the current node then you know that now you need to search in left subtree in-lap subtree first you need to see if you have any slab subtree okay so if self dot left now one possibility could be in left sub-tree you don't have any element left the element that you're searching for well doesn't exist okay in that case what's gonna happen is it will go to else and it will return none okay so you can say return none but well you don't need to write this code if it goes to else is gonna return none anyway that's a default behavior of Python functions so I'm not writing it okay let's say in left hand side you have a subtree so what you want to do is you want to recursively call delete method on your left subtree if value is greater than self the data then similar code you want to check first if there is a right subtree or not and if there is then you want to on that subtree see that's why I'm doing self lured right delete so on that subtree I'm recursively calling delete function asking it to delete well again if you don't have anything you can just simply return none but Python will do this for you automatically so you don't need to write this all right now the most interesting case is this correct here if self dot left is less than none and self dot right is also known then you can return none because now you reached your last data point okay let's say you are already the leaf node and your left and right subtree is basically none then you can return on otherwise okay I don't need to write else if actually I can just say if self dot left is none so here you have right but you don't have left in that case you can return self dot right in the theory part we saw this case number two where you have only one child so in that case you can just return that one child back to your parent node so that your current node gets deleted and then if self dot right is none returned self dot right I hope this makes sense you know recursive function calls requires some particular mindset so it might take some time to get used to it if you are new to recursion but as you practice more you will get a feel of it okay now I mean here when I'm at this point I have left subtree right subtree so one of the strategy is you know from the right we study in the theory from the right subtree find minimum value okay so let's say this gives you a minimum value and that minimum value you can put in your current node okay so if you remember from our presentation the copy minimum from right subtree see right subtree had 23 here so this 23 we copied here here okay so now I had to placate nodes but 23 here so 23 so this images 23 is here what was the next step after you copied well you were deleting a duplicate node so this particular duplicate no 23 I have I need to delete so how do I delete it well I can say self dot right from my right subtree delete what do I want to delete delete min bath so 23 was copied to current node and now I want to delete it and that this is important that you need to copy to right basically the is gonna return you the new right subtree which you need to copy to self dot right okay and then in the end you return self all right so let's taste this method and see how it looks now we needed a helper method to build a tree so I'm just copying it from the part one tutorial nothing fancy about it and I'm gonna write my main routine where I built a tree like this I want to delete number 20 okay so if I'll delete number 20 let me just show you so if you look at the presentation when I delete 20 okay after I delete it my tree should look something like this it should have this kind of structure so let's see if our code is doing that or not so how do you verify that well you can print the tree by doing in order traversal just to make sure ok so right click run binary tree and see when I ran it you can see that I had a 20 element before but now I do not have 20 here if you want to visually look at it the best feature in pycharm is this debugging so you set a breakpoint here right click debug and you will be able to see your tree I mean - won't be as visually appealing as our presentation but see you have 17 here okay let me show you how yeah it's gonna look something like this so you have 17 in your left subtree you have 4 1 9 the right subtree you have 23 18 and 34 so let's confirm right subtrees first so i had 23 18 34 see 23 18 34 that's what we saw here and left subtree has 4 1 9 so have four one nine so this is working as per our expectations okay and another like we can run couple of use cases here and see if it works okay see deleting nine so deleting nine is the case we saw before where if you delete nine here it's going to look like this okay so there is some problem here I deleted nine but after deleting nine I still see that in this list so let's see what is the problem okay here I need to assign self not left because after you delete it you want to assign a new subtree to yourself dot okay and run this again and you can see that after deleting nine I don't see that nine here anymore twenty I don't see here in seventeen I don't see here all right now the most interesting part of this tutorial which is an exercise guys you have to do exercise if you don't do exercise then you're wasting your time don't watch my tutorials go watch some movie on Netflix you have to do this exercise period the exercise here is the class that we implemented in this tutorial we used minimum elements from the right sub-tree to replace the current node and these are the three lines where we do that you have to remove these lines and use maximum value from the left subtree and and re-implement this delete method and make sure it works okay I have a solution link here by the way but don't look don't click on that solution link otherwise it will download the virus in your computer so if you have already worked on it on your own then only look at the solution and verify your answer with my answer this should be pretty straightforward if you remember from the presentation we had two approaches either finding minimum from the right subtree or maximum from the left subtree so I implemented one now I leave it on you to implement the second approach if you liked this tutorial give it a thumbs up share it with your friends data structures are very important during interviews and implementing data structures in python is going to be super fun so share it with your friends and give it a thumbs up and leave a comment in the in the section below if you have any questions in the video description I am going to provide you the link of this exercise the solution etcetera okay so go download it from github thank you