Delete Node in a BST - Leetcode 450 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem delete node in a binary search tree we're given the root node of a binary search tree and a key value and we want to delete the node with the key value of course and then we want to return the new root of the tree maybe the root changed maybe it didn't that's kind of what they tell you here it's pretty rare for leak code to give you a hint like this but you got to take what you can get and they even give you how to break down this problem you have to search for the node that you want to remove and then remove the node if only it were that easy though this problem can be surprisingly tricky the first time you solve it especially if you don't have like a deep understanding of how binary search tree operations work but we can use the properties of bsts to our advantage let me show you how I'm going to do that we're given the root of the tree we're given a key 3 in this case we want to find it now finding it is not going to be too bad we know we can do that in log n time well that's assuming the tree is balanced it might not be balanced so actually a more correct way to say this we can find this by using the height of the tree that's all we're gonna have to Traverse but after we find it we also have to delete it finding it is easy we just take the root value 5 is 3 greater than five nope is it less than five yes it is less than five so we search to the left and we would recursively just keep doing that until we find the value now hypothetically the key value might not even exist in the tree in that case we don't have to do anything so that's pretty easy but in this case it does so what do we do with the value once we have found it of course we want to delete it you might first think that well you got to get rid of this node and you got this pointer over here so instead of pointing it at three we should point it somewhere else and we have to like move these nodes around that is technically possible but if you even try to code it up this way you're going to quickly find out that it can get pretty complicated because once you get to the three you're still going to need a reference to it parent so that's going to be kind of complicated there's actually an easier way to do this it's a bit clever and that is we can replace the value of 3 with a different valid value we could pick any value in this tree Why not pick the 7 over here let's get rid of this seven maybe just delete this node and then put a 7 over here well there's two problems here one when we put a seven over here does this still look like a binary search tree to you not to me because every value over here should be less than five but that's not the case seven is greater than five so that's the problem we have to preserve the properties of a binary search tree and second well if we put the 7 over here then we still have to delete a different node anyway so how did that happen how can we prevent that or maybe there's something clever that we can do and yes it turns out that there is something clever first of all what value should we replace three with we should probably pick a value in this subtree if there's one available to us the the reason is because we know every value in this subtree is already less than five so we are allowed to replace this value with two or four but we really have to think through a bunch of edge cases for us to choose the most intelligent value let me tell you why first of all what would happen if this three over here actually did not have any children well in that case it would be pretty easy to delete this value because what we're going to do recursively I'm going to tell you that we're going to solve this problem recursively because it's a lot easier to do so what we want to do is recursively delete from this tree and then recursively delete from this tree Once We delete from this tree we want to return the new tree up to the parent and then we want to return this tree just from our outermost function call but what would we return from here once we delete three we would return null of course and this null value that we're returning is what this parent is going to assign to its left child whatever we return from here is what's going to be assigned to the left child of five so basically what I'm getting at here is if 3 has no children we return null what happens if it only has one child though what if three only has a single child two now this child could have some children or it might not have children I'm arguing to you that whether it has children or not doesn't actually matter for us because we know this itself is a binary search tree and if we get rid of three all we have to do is say that five's new child is two which is a binary search tree and every value here is going to be less than five and of course the exact same thing would be true if three did not have a left child but instead had a right child only and maybe it had some children or maybe it didn't it wouldn't matter we would replace it with this new sub tree regardless so to summarize a really elegant way to write this code code would be if 3 does not have a left child return the right child what if the right child doesn't exist that's okay because this is null and that's exactly what we want to return to the parent anyway and if three does not have a right child we return the left child because if it exists we return it great if it doesn't exist we return null which is what we would want to return anyway so that was the first step now let's go on to the second step which is a bit more tricky I think now of course in this example we actually do have two children for three so what we actually have to do is replace the value we have here we can pick a value from the left subtree or the right sub tree this is a pretty simple tree and I can't really add additional values to four because I can't really add a one that would not make this a binary search tree but just pretend like we have some dummy value here that is valid and some dummy value here that is valid as well what we would want to do logically is pick an intelligent value from the right subtree what value could we put here such that it would satisfy this being a binary search tree if we pick four and put four over here it's actually not going to be a binary search tree because this value is supposed to be less than four that's why it's the left child but if we put 4 here then X is over here x is actually less than 4 but it's on the right sub tree that's not what's supposed to happen so when we pick a value from this right subtree which is what I'm going to do you could pick one from the left subtree but I'm going to pick one from the right subtree I'm going to pick the smallest value aka the minimum value from the right subtree every value in the right subtree is greater than 3 but we want to pick the smallest value because if we pick the smallest value then we know that every value here is still going to be greater than the value here now how do we find the smallest value from the right subtree that's the easy part about a binary search tree you just basically go as left as you can you just keep going in the left Direction you keep going left until you can't go left anymore that's the minimum value and then you put that minimum value over here in this case it's going to be four and then what you do is recursively and this is kind of the hard part you probably wouldn't think of by yourself you recursively call delete node on the right subtree over here because remember if we put 4 over here now we have two four values that's not what we wanted so we have to recursively call delete node on the right subtree passing in not three anymore we're not trying to delete three now we're trying to delete four so in that case we will actually end up with a chain of recursive delete node calls first we delete the value three and then we want to delete the value that we replaced three with so then we want to delete four and it's actually possible that four had a right child let's say it had a right child of five even though five is already here let's just ignore that but if it had a right child of five we'd put the four over here because 4 is the minimum we can't go any further to the left but now we want to call delete node on this tree passing in four so then we get to the four now we want to delete this four so we again pick the minimum value from the right subtree which in this case is five we would delete this node and then we would put the five over here and then we would call delete node on this subtree deleting the five and then possibly we would just keep calling that recursively but the smart thing here is that we are pretty much iterating through the height of the tree as best as we can there are portions that we are going to have to visit twice but if we have to visit a portion of it twice the worst case this would be two times H so still the time complexity is the height of the tree now let's code it up that was a long-winded explanation but the code is actually not too bad so generally with recursive problems we want to start with the base case so it if the root is null then we just want to return the root there's nothing for us to delete anyway otherwise we want to find the node that we want to delete so if the key value is greater than root dot val then we want to go to the right which we can do like this so self dot delete node passing in root dot right passing in the exact same key value else if the key value is less than root dot val then we want to call delete node on the left side of the tree so on the left subtree passing in the exact same key value now the last case is that we actually found the node that we want to delete so this is where we actually do the deletion now you might have forgotten but remember there's actually some simple cases root is the node that we want to delete but what if the left child of root is null then in that case we know the new subtree that we want to return to the parent is going to be root dot right we don't have to do anything super fancy and otherwise if the right subtree is null then we return root dot left which actually reminds me when we call delete well first of all over here we should call this delete node and when we actually call these deletions we might be deleting the left child itself so we probably want to take this updated binary tree and assign it to root dot left imagine if this was the base case that executed instead of returning the root that was actually passed into this function now we want to return root dot right so in that case we would want to take the return value of this call and assign it to however it was called whether it was the left child or the right child so let's do that up above as well now for the slightly more complicated part so now we want to find the minimum from the right subtree just like I showed earlier the easiest way I think to do that is just to take the current pointer and assign it to root because we are going to still need the root and then while Kerr dot left we're gonna keep going down the left child the reason I'm doing this is because we want to make sure we stop at a valid note we don't want Cur to stop at null so by the time this is done Cur should be pointing at the minimum node in the right subtree and remember what we want to do with that minimum value is replace the current root value with it so we say root dot val is equal to curve.val and then we want to delete that value because now we have duplicates we want to delete that from the right subtree exactly where we found it so we say delete node on the right subtree using the value not key we're not using key anymore now we're using the root dot val or you could say occur.val because they're the exact same value I'll just do root dot val and then remember the return value of this we should probably assign it to the right subtree still in case it ends up changing now remember regardless of which one of these three executes we want to return the root node either way you might have the first time you wrote this similar to me you might have had you know return statements here and here as well but then you realize you're returning the same value so you can delete the line from here here and just have one outside of all three of these now let's run this to make sure that it works okay really sorry about that I had a couple mistakes here where we're assigning Cur equal to the root that's not what we want to do of course we want to go to the right subfree so we're going to say Cur is equal to root dot right and here when we're iterating through the loop we're not really doing anything hopefully you caught this one as I was writing it but we want Cur to be equal to cur.left as we go down so now let's run the code and as you can see it's pretty efficient if this was helpful please like And subscribe check out neat code.io if you want to see code solutions for languages other than Python and for a bunch of other free resources to help you prepare for coding interviews thanks for watching and hopefully I'll see you pretty soon