Cousins in Binary Tree II - Leetcode 2641 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem cousins in binary tree 2 so I'm just going to jump straight into the example because this problem isn't super complicated conceptually at least so the idea is we are given a binary tree like this we want to modify the value of each of these nodes such that we take each value and we replace it with the sum of pretty much every other node on that level so I'll actually start with this level just to make things clear this level has a sum the sum of the entire level is 18 so for each of these nodes we don't want to replace them with 18 for this node for example we want to get the sum of all other nodes in that level except for like the node itself and The Sibling of that node mean meaning that like if this and this are sharing the same parent they are siblings now this one doesn't have a sibling so this one is going to be replaced with the sum of these two so that's 11 for this one it's going to be replaced with this which is seven and for this one same thing it's going to be replaced with this it can't include this one because that's its sibling so it'll be replaced with a seven so that's how we're getting this this and this so obviously two nodes that are siblings are always going to have the same value after we modify the tree now how exactly do we compute that how do we know which value is going to go here like in terms of the level sum well you could think of it this way a node is going to be replaced with the level sum minus itself and its sibling if it has a sibling so yeah I'll just say minus A and B and those are going to be the nodes themselves so this is how we can solve the problem suppose we compute the level sum for every level so it's a five here it's going to be 14 here and then here it's going to be 18 we can do that most easily with a breath for search Pretty Natural tree traversal algorithm to compute this we could also do it with a DFS but I prefer BFS in this case so now we are actually going to Traverse the tree a second time and this time again we could do either DFS or BFS I'm going to do BFS just cuz that's the way we did it the first time anyway so it doesn't really matter this time for every node we're going to take the level sum minus this value like the original value in that node and its sibling if it has one this one doesn't have a sibling so this is going to be 5 minus 5 so it's going to get a zero over here then we're going to go here same thing the level sum is it's not 14 it's 13 I'm sorry about that so 13 - 4 and it has a sibling 9 so - 9 as well we're left with zero so same thing over here 13 - 9 - 4 We're left with a zero we'll do the same thing for these as well so you probably get the idea the only difficult part is for a node how do we get the sibling of that node now there's multiple ways to do it we could save pointers we could go look at the parent and then look at its other child there are many different ways to do this in terms of BFS the easier way actually is like this suppose we're at this node as we are adding its children to the Q with BFS that's generally how BFS works with a Q so that's when we're actually going to update the values of the children not when we're actually visiting the children themselves but when we are at the parent so from the parents perspective we can see that we have two children so we can get the sum of those two children which originally is is 4 + 9 and that's 13 and then from that we can subtract the level sum well we can take the level sum and subtract from that the child sum and then that'll be the replacement value so from here we would see that the level sum is 18 the children sum is 1 + 10 that's 11 so we can take 18us 11 that's the value that both of the children of this guy are going to get so there's multiple ways to do it and I think this is a reasonable approach and the the time complexity since we are traversing the tree twice is going to be Big O of n * 2 that is linear time though in terms of space it's going to be Big O of n cuz that is the worst case uh memory complexity for one of the levels in the tree so let's code it up so this will be a nice two-phase algorithm where we will first compute all the level sums into an array so let's do a BFS for that we will create a deck and we will initialize it with just the root I just realized I didn't really explain too much what BFS is I have plenty of resources on that I have plenty of YouTube videos and you can also check out this course where it goes through a breath resarch pretty in- depth has a lot of like animations and all that stuff so you might find this useful if you're a beginner uh But continuing we can say while the Q is nonempty we are going to compute the sum at the current level we'll initialize that to zero and we'll say okay for every node currently in the que so we're going to take a snapshot of the length of the Q so just to go through every node in the current level we're going to pop q. pop left we'll get the node we will take the nodes value and add that to the current sum and after we're done Computing the current sum we will append it to the level sum like this and we need to continue the BFS here so if the current node has a left child we can say this pend it to the q and we can do the same thing with the right child if it has one we can append it to the Q so that's pretty much it for the BFS the reason I can do it so quickly is because I've written this like probably over a 100 times so it just comes with practice and now let's do the second phase where we are going to take for every node and replace it with the level sum minus the node and its sibling there are many ways to code this up in Python I'm going to first do it this way and I'll show you like the other way as well so let's say we have a deck I'm going to pend to that CU just the node but actually if I do it this way if where if I have the node and The Sibling sum like the child sum of that node and its sibling then it's pretty easy to code it up so we can add a tupal here where the node and the child sum and for this node itself it's just going to be the value because it doesn't have a sibling of course now coding it is going to be very easy we're going to keep track of the level initially it will be zero and I'll say while the Q is nonempty again I'm going to go through every node currently in the level so snapshot of the length of the que I'm going to pop from the que and this time I'm going to get two values I'm going to get the node and I'm going to get the child sum value so that's what I'll call it actually I'll call it a value for now so we're going to replace place that node's value with uh the level sum at the current level like this subtracted from it that other value that we just popped which is like The Sibling sum pretty much so actually let me I'll leave it as Val but probably a better name for it would have been sibling some so this minus Val now for our children we want to continue the BFS so we're going to have a couple if statements like these so I'm just going to copy and paste these for now but when we append to the Q now we're actually appending a tuple so to this Tuple I want to not just append the node but I want to append the sum of this node plus its sibling if the sibling actually exists so both of these are going to get the same value uh the second value appended to them if they both exist assuming and let's call that the child sum so I'm going to put that here and I'm going to put that here now we just need to compute what that is I will initialize it to zero and I'm going to need a couple if statements to compute it if the left child exists we will add to it the value of the left child so let's say child sum add to it node. left doval and then let's do the same thing for the right uh child as well so we're doing this from the perspective of the parent because from the parent we have access to both of the children but from the left node we would not have access to its sibling the right node so here I'll change that to a right so with these two if statements we will compute the child sum and then we will append the child sum here unfortunately we can't combine these if statements very easily because we need to compute the sum before we can execute either of these and we only want to execute each of these if that node actually exists so I think this is like a sufficient way to code it up last thing down here let's not forget to increment the level and then down here we are just going to return the original route of the tree we already modified the value of it so we should be good this is pretty much the entire code so I'll go ahead and run it and you can see here that it works and it's efficient I will show you a slight variation of coding it this way if you don't want to append a tuple to a q or just depending on the language that you're using if you can't do that we can modify this approach to just uh add a single value so just the root we can rather than updating the value after popping from the queue we can do it this way so here we won't have this one since we're just popping a single one we will do this we will still have the child sum and rather than just appending the child sum to the Q we can just use it at this point so we're getting rid of this because we just want to add the node itself now and getting rid of this part before we append that node we can update the value of it I mean we could also do it after it doesn't really matter if you put the line here or here but this is how you would update it you would say node. left do value is going to be equal to the level sum at uh the current level it probably wouldn't be the current level at this point it would probably be the level + one because if we're at level zero we're at here and we want to update our children we would want the level sum of the next level but that's what this is and then from that we'd want to subtract from it uh this value and uh the node. write value which we already computed up here in child sum so we can do this and so I'll copy this to put it down here cuz it's going to be the exact same for node. right and so now we're almost done the only thing we're missing here is that we started with the root node we po the root node and then we update the values of the left and right child but we never update the value of the root node but the value of the root node is pretty trivial to update it's always going to be zero so we can say root. value is equal to zero so unless I have any bugs I think this looks good let me run it and yeah you can see it works and it's also efficient if you found this helpful check out NE code. for a lot more thanks for watching and I'll see you soon