Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum time to collect all apples in a tree we're given an undirected tree consisting of n vertices numbered from 0 to n minus 1 but to be honest the numbers aren't really important it's important that each of them has a unique label and we'll be using that now some of the nodes could be empty but some of the nodes the red ones in particular will have apples on them and our job is to collect all of the apples now before you start coding it up this is actually not a binary tree even though all of the examples on leak code look like binary trees this is more of an arbitrary tree so this is actually more of a graph problem in my opinion instead of being given a tree node we're actually given the edges forming the graph that's kind of why the label of every single node is important here so our job is to return not the sum of these values not the apples and totaling them up but actually it's to sum up the time it's going to take for us to collect all of the apples how do we calculate that time because obviously to collect these three apples One path as shown on the diagram is starting at the root we're always going to be starting at the root but from here we could go left and then left again and then back up after we've collected that guy go back down come back up after we collect him and then go back up to the root and then go down to the right child and then go back up there's no need to visit these guys because there's no apple here and there's no children so there's no apples down here now obviously we could have gone the other direction as well we could have gone right first and then came back and then went left it doesn't really make a difference whether you go left or right first as long as the edges are correct we only visit and travel along edges that we need to and what we're actually returning for the total time is basically the total number of times we had to Traverse an edge so we went down one two back up three down four up five up six down seven and then back up eight so we would return eight in this case and you can see that's what happens here so this problem isn't super crazy that's pretty much all we're doing here but now how do we actually code this up we don't know whether a path like we don't know whether this right sub tree actually has any apples or not until we Traverse them so we are going to have to Traverse the entire graph so the overall time complexity we should be able to get it down to the size of the graph which is n let's say we have n nodes technically each Edge might be traversed twice so you could say it's two times n but we know that you know still reduces to being a linear time algorithm now let's blow this up and I'll show you how we're going to solve this problem we're going to do it recursively there are multiple ways to do it but I think the easiest is to do DFS now remember this is not just a traditional tree this is actually a graph so first we're going to take these edges and build an adjacency list an adjacency list basically means for every node we're going to get its neighbors now this node has two neighbors the one and the two and what about this two it has three neighbors actually it has a child here three a child here six and a parent one that's the most number of nodes any single node is going to have that's the most number of neighbors and you know it is going to have and we don't really make a distinction between parents and children all we know is we're starting at the root and that's all that really matters so this is how we're gonna run the DFS we're going to start left and basically recursively we're going to visit every single node in this tree and we're gonna ask the question how many uh seconds or whatever time unit we're using how much time would it take to collect every single Apple in this sub tree well starting at one how much time would it take to collect these apples well we'd have to go down to four and and then from four recursively we would of course ask how much time is it going to take to collect all the apples down here well the good thing is it doesn't have any children so the time it takes is zero and from four itself what value would we return to the parent would we return two because from one we're gonna have to go down here and then go back up but if we're starting from four that doesn't really make sense to collect all the apples from here it would just take zero time units but then going back up to the parent we know that it actually took two time units to collect this Apple so how do we kind of get around that how do we make sense of this well what we say is we know it took zero time from four to collect any additional apples but we know for itself had an apple because we have an input array that tells us which nodes have an apple or not and that's called has Apple and so we know that this does have an apple so at the very least we know for sure that starting from here we had to go down to four and then back up so we know for sure we're always going to add 2 if there is an apple in the child's spot and the exact same thing is going to be done going from one to five five does not have any children so it takes zero time to collect all of these apples down here because they don't exist but to go down to five and then back up it took two time units and we definitely had to do that because we know for sure five had an Apple so what value would we return from one going up to our parent how much time did it take from here to collect these apples it took four time units from one and then going back up to zero the value we would return to this parent is four but again we would add two to that to get a total of six because we know we did have to go down to one and then back up what one tool does is how much time it took to collect these apples but the plus two comes from the fact that we did have to go down here and then back up and we know we had to do that not because the child had an apple and this time actually one did not have an apple so how do we know that we actually did have to go down here and then go back up how do we know that well we know that the return value in this case was not zero it was four so we always add the plus two we always add it as long as the return value is positive or the child itself had an apple that's our criteria and doing the exact same thing quickly on the right subtree from here we go down to our child two then from two we go down to our left child three how much time is it going to take to collect apples from here well it doesn't have any children so we return 0 and then from two we see that we got a return value of zero but we also see that the left child does not have an apple so that must mean there does not exist a single apple and the entire left subtree so we don't add anything we add zero and then the exact same thing with the right subtree there's no apples down here so we add 0 to the parent so what value do we return from here we return zero it doesn't take any time to collect all of these apples but from the perspective of the parent it got a return value of zero but it also sees that the child itself has an Apple so we do add that plus two so from the left subtree we get six from the right we get two and then total we get eight that's what we're going to return clearly we just have to iterate over the entire uh tree time complexities because of n okay now let's code it up okay so now let's code it up and the first thing like I said I'm gonna do is create an adjacency list and I'm basically going to initialize it with the key value the key value is just going to be a node and then every node is going to be mapped to initially an empty array so for every position for every I in range range n we're given n which is the number of nodes in our tree slash graph and next what I'm going to do is for every Edge we have a parent and we have a child and using that we're going to say that the parent has a neighbor so we're going to append the child to it and we know the child has a parent and we're going to append the parent to it I guess the parent child naming is a bit misleading because really these are just neighbors but it doesn't matter too much in this case you might be thinking why do we need to for the child also add its parent as a neighbor we're not really going to be going up the tree recursively we'll be able to go up the tree but we don't need to explicitly travel along an edge and you'd be right but one of the test cases confusingly does require you to go from the child up the chain because when they tell us it's a tree that basically just means it's an acyclical graph there's no really parent-child relationships that we need to concern ourselves with we do need to recursively Traverse this tree so we're going to write our recursive DFS function and we want to make sure we don't get stuck in an infinite Loop so we could have like a visit hash set but the only main way we'd get stuck in an infinite Loop is if we keep going from the parent to the child and then from the child back up to the parent so the only parameter that we need to pass in to not get stuck in a loop is for every node we just need to pass in its parent along with it so that we don't end up going back up where we came from but other than that no major base cases we don't have to worry about null nodes thankfully we are going to initialize our time which is going to be the return value how much time does it take us to collect all of the apples uh then we're going to go through every child in the children or neighbors of the current node now this is where we prevent the infinite Loop If the child is equal to the parent then we want to skip this we don't want to go back up to the node that we just came from and you'll see where the this parent comes from when I actually do the recursive call right now so if this is not the parent then we are going to Traverse it recursively so we're going to run DFS on this child and what's the parent of this child it's the current node that we're currently at so the return value of this recursive DFS call is going to tell us the time it took to collect all apples in the subtree I'm going to call that the child time on this child subtree that's how much time it took us to collect all the apples now only if this value is positive would we actually want to add it to the total amount of time the child uh yeah the total time remember we also want to add 2 plus the child time because the child time doesn't tell us how um it only tells us how much time it took to collect the apples within that subtrue not how much time it took us to travel to that subtree itself now it's possible that the child time was Zero but the child node itself did have an apple how would we know that well we do have an input parameter has Apple so we know for every node does it have an apple or not so what we're going to say is if either the child time is non-zero or has Apple this child itself has an apple then we're going to run this but what would happen if the child time was Zero but the node had an apple well this would evaluate to 2 plus 0 which would just add 2 to the total time so you can see that it does work out in both cases you could write this out with like two if statements or if else statement if you'd like but this is just kind of a clean way to write it or a neat way you could say that's pretty much the entire function though when all that's done we just need to return the total time and then outside of this recursive function we're going to call DFS we're going to call it on a node 0 that's our starting point that's provided to us and the pair parent initially zero doesn't really have a parent we can assume so we'll just pass in like a default value of negative one and uh we're just going to return the result of this let's go ahead and run that to make sure that it works and as you can see yes it does and it's very efficient if this was helpful please like And subscribe if you'd like to see the code solution for languages other than python check out neat code.io it's got a ton of free resources thanks for watching and hopefully I'll see you pretty soon