Delete Leaves With a Given Value - Leetcode 1325 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem delete leaves with a given value we're basically given a binary tree and some energer Target and we want to remove it from that binary tree the only catch is well first of all there could be multiple nodes with that value that's number one second of all we only want to delete the nodes with that value that also happen to be Leaf nodes so for example look at this node over here it's two but it's not a leaf node but look at its left child it definitely is a leaf node doesn't have any children and the value is two so that's the one we're going to remove now the thing is as we remove nodes for example if we delete this node you can clearly see that this node doesn't have a right child and we deleted its left child so now this is a leaf node so now we delete this node as well so that's kind of the hard part about this problem some nodes might not start out as Leaf nodes but they can become Leaf nodes and I just want to mention that this is not a binary search tree remember that not all binary trees are binary search trees so we do have to Brute Force this solution we can't intelligently search for the twos so this is a tree problem and as you know generally tree problems can be solved with the traversal algorithms DFS BFS I'm going to start with DFS as usual and if it doesn't work then we usually go to BFS but usually it does work and in the context of this problem based on what I said earlier what kind of DFS traversal do you think makes the most sense like of the ones that we know the common ones are like in order pre-order postorder which one do you think makes the most sense to me pre-order definitely doesn't make sense because why would we check uh should we you know delete this node over here why would we ask that before we've traversed the left and right subt trees because it's possible we might delete the entire left and right subtrees and at that point we would want to ask should we delete this node so pre-order isn't the way post order is the way and that's pretty much the entire problem so let me just kind of briefly explain the recursive logic of how to solve this problem we'll code that up and then after that we're also going to solve the problem iteratively it's similar to yesterday's iterative solution but I will say this one is definitely more challenging so it's a good test of our abilities so we'll get to that as well so with postorder traversal we start at the root and before we even look at the root we're going to go to the left sub tree and then we're going to go to the right sub tree so let's start with the left and in this case the target is three I kind of deleted that text but the target is three that we're trying to delete so then we go to the left child again we don't even look at this guy yet we go to the left child once again and here we try to do the same thing left child okay and right child nope not that either okay so then we look at the value finally it's a leaf node and the value is three so we want to delete it but the question is we're at this node to delete the node don't we have to set the parents left child equal to null so the question is how do we do that recursively it's kind of weird well the easiest way is this there's either two cases either we delete this node in which case the parent's left child should be set to null the other case is we don't delete this node in which case the left child should stay as whatever it currently is so the easiest thing to do is just return null if we delete the node and return the node if we don't delete it and then in the parent when we call DFS I'm just going to quickly write it as DFS when we call that on root. left we're going to assign the result of that recursive function to root. left itself so maybe it changes maybe it doesn't change but this is the easiest way to do this and this is pretty much the entire problem we'll do the same thing of course with root. write as well and after we are done with both of those recursive functions only at that point are we going to then check if is the parent like once we've gone through the left we deleted it we didn't delete the right child so it stayed the same then we're going to look at the parent and say okay does it have a left child no does it have a right child yes so therefore we can't delete this node even though the value is three so that's pretty much for the left sub tree for the right sub tree it's going to be similar it's three no children so delete this node and then we return up to the parent we deleted this guy but it still does have a left child so we keep this here but it's a one anyway so even if it didn't have any children we would still keep this anyway just to briefly go over this example here we're going to you know just keep going down recursively we're going to get to two Okay we have to delete it therefore we're going to return null to the parent then the parent will not have a left child it never had a right child to begin with therefore we're going to delete this as well by returning null to the parent and then you know you can kind of just imagine that we're just going to keep repeating that until we get to the root and the only reason we don't delete the root it doesn't have a left child it doesn't have a right child the only reason we don't delete it is cuz it's a one that would be the ultimate result okay let's code this up the overall time and space complexity is going to be Big O of n because that's just how a tree traversal works we visit every single node and in the worst case the tree itself could be like this node down here where it's pretty much a linked list this tree is pretty much a linked list so the height of the tree is n therefore the space complexity is going to be Big O of n because that is going to be the recursive call stack size okay so to solve this recursively let's check first of all the base case typically where cursive functions is with trees is the root null if it is we should return but remember the return value in this problem does matter I think by default this is kind of just going to be null anyway but just to be explicit let's explicitly return null next remember this is post-order traversal so we want to do left sub tree right sub tree and then look at the root so let's set root. left equal to remove leaves from the left subtree and remember there actually is a second parameter in this problem don't forget about that so let's pass in the Target as well so we're going to do the exact same thing on the right subtree just a quick copy and paste job there and now for the interesting part what should we do well there's two cases either this is a leaf node so not root. left and not root. right and not only that but the value also has to be equal to the Target we're not deleting every leaf node only Leaf nodes with the target so now call how do we delete again well we just return null how do we not delete like if this doesn't evaluate to true then what should we do probably just return the original node this is pretty much the entire solution at least doing it recursively and as you can see on the left yes it works it's pretty efficient okay so now let's do the iterative postorder solution we generally use a stack for that for reasons I kind of explained in yesterday's video to mimic like the recursive call stack and we start with the root node on the stack remember that when we pop this one we're at this node but we don't want to visit this node just yet we want to go through the entire left subtree and the entire right sub tree and then look at this node and the value of that node so how do we kind of mimic that functionality with an iterative stack well same as yesterday's answer when we pop a node like this one we want to know if this has been visited or not the first time we pop it it hasn't yet been visited then we will mark it visited and I'm going to use a hash set to do that cuz the context of this problem is slightly different than yesterday so a hash set should be sufficient so now we're going to say that one has been visited it's true and obviously there's duplicates in this tree so I don't really know a good way to differentiate that down here but basically one has been visited now at the same time it wasn't originally visited we would have looked it up it wasn't originally there so before we add it to visit we would say let's add one back to the stack and let's add its children to the stack the order that we add the children in doesn't matter but we do have to make sure we add the parent first because Stacks are going to be popped last in first out so now we pop this guy let's assume it's this one over here and pretty much same thing we're going to look it hasn't yet been visited let's go ahead and add it back to the stack and add its children to the stack 32 and let's mark three as visited I guess the best way to mark them visited is just going to be to draw it like this to be honest and now suppose we pop two two is a special case it's a leaf node so in our code we can detect that pretty easily just by checking that it doesn't have any children so even though it hasn't been visited who cares it's a leaf node let's go ahead and just process it anyway let's look at the value it's a two but we're looking for threes so we don't delete this we leave it as is since we've right now just been going over how to do Post order there is another component to make this work we have to like when we're actually deleting a node as you're going to see here now we're going to pop this guy we're popping three this is also a Leaf node and it has the target value so we want to delete it but how do we delete this guy well we would ideally want to set the left pointer of the parent to null so how the heck do we do that the easiest thing and I didn't really show it as we were going we're going to have a third data structure it's going to be a hash map I'm going to call it uh I guess parents basically going to be a parent map it's going to map every single node to its parent that's very easy to build is it like as we start at the root and as we Traverse the tree we can just add the parents like when we are at one and we add three and this guy to the stack at the same time that we do that we can say that the parent of this is one the parent of this is this node let's just assume we have a mapping for that by the time we get down here so if we assume we do have that mapping then very easily we can just say for the left parent here set it to null and we'll know that this is a left child and it's not a right child because we can pretty much just do an if statement for that we can check okay the parent is this either the left child or is this the right child that'll be easy enough to do and so this will be pretty much deleted from the tree in that case and that's more or less the main idea of this problem the only thing is what about the root node what if we had a tree that looked like this but the root was also to delete this delete this delete this and delete the root node but how do we delete the root node with the way I explained this it doesn't even have a parent well we can add an if statement in that particular case to detect that to check the root doesn't have a parent in this hash map we'd probably set the roots parent equal to null and in that case we would probably just return null so as you can kind of tell this solution is going to have quite a few if statements but the overall time complexity and memory complexity is going to be unchanged the stack is going to be responsible for the memory obviously well I guess all the other data structures as well okay so I'm going to go ahead and declare our stack and initialize it with the root I'm also going to have those other data structures the hash set to Mark nodes visited and a parents map which I'm actually going to initialize like this root is mapped to null for reasons I kind of talked about a second ago since the root obviously doesn't have a parent then we're going to have a loop while the sack is non-empty let's pop a node from the stack and first things first let's just check if it's a leaf node if not node. left and not node. WR we'll have an else statement over here for if it's not a leaf node so if it is a leaf node then we want to check another thing is this the Target that we're looking for if it is let's go ahead and delete it how are we going to delete it well let's get the parent we'll assume we just have a pointer to that in this map and then we want to check first check if this is the root node so if not P that means it doesn't have a parent so it must be the root node in which case we're just going to return null other case is it's nonnull and then we just have to figure out if this is a left child or a right child so we're going to check the parent is the parents left pointer equal to the current node or maybe the parents right pointer is equal to the current node so in the first case we'll do p. left is equal to null in the other case we'll do the opposite P do right is equal to null so this is how we are deleting the node we're pretty much done with that this is pretty much the base case of what we showed in the recursive solution and this is going to be the opposite this is going to be the recursive step one thing is that if this is not a leaf node we want to mark it as visited right and I guess we could have done that up here as well but there's really no need to Mark like a leaf note as visited because we're probably not going to visit it twice anyway but the reason I'm not putting this line of codee up here is because we actually need it for this like in this step is when we're going to say stack. append the current node and we're going to say if the left node exists append that as well and we're going to say obviously if the right node exists go ahead and append that as well so obviously we'd only want to do this part a single time how do we prevent our eles from doing it a second time well obviously we need some kind of guard rail that's what visit hashset is for in the first place so one thing I'm going to add to this condition is else if node is not in visit only in that case are we going to Market visited and do this portion now the only thing I haven't done I think is actually update the parents themselves can you kind of guess where that code would go probably uh this part where we're going from parent to child so if we're adding this to the stack before or after I guess we could say parents node. left is going to be equal to node that's the parent of this node down here it has the same parent the right node also has the same parent and this is pretty much the entire code it's quite a lot mostly just because of all the conditionals to be honest the other case is we might not necessarily be deleting the root node so if we don't do that let's out here return the root node where maybe some of the children in that tree have been deleted so let's go ahead and run this looks like I was going too fast and forgot my double equals for these conditions sorry about that okay now you can see that it does work it's pretty efficient if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon