Distribute Coins in Binary Tree - Leetcode 979 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem distribute Leos in a binary tree it's almost like I can read the future or something sorry I'm sure half few people don't even know what I'm talking about but uh we're given a root of a binary tree with n nodes the value of each node will represent the number of coins that it has this one has three this one has zero and this one has zero now the total number of coins is actually going to be n equal to the number of nodes that we have so the question becomes can we distribute these coins among the tree so that like there's a single coin at every single node well of course we can that's definitely possible and the way it's going to be done is any node can pass coins from itself to either of its children and a node can pass coins to its parents so basically every single pointer is traversible it can be used to transfer coins now if I were to take one coin and pass it to the left child here that counts as one move if I were to take two coins and pass it to the same node that would count as two moves I don't know why I would do that to this node but I'm just saying that that's kind of the rule of this so if I pass one coin here one coin here that's two moves total I guess let's look at this example if I were to pass two coins to the parent that's two moves now this node has two so it actually has an extra this one has one so now what we do is pass one coin down here and then that's going to be three moves total whereas this one was only two moves total first things first this is clearly a tree question so we pretty much know some kind of traversal DFS or BFS is going to be useful we almost always default to DFS so let's kind of do that one more time but I want to say that this is not like a trivial tree problem many tree problems are just pretty damn trivial in my opinion when you just solve them with DFS or some kind of recursive solution this one is not and there's a reason for that and I think you know if you're a beginner even if you're able to solve this problem you might not immediately know why this one was a little bit more difficult than all the others I'll try to explain that and I will try to give you the intuition not just the solution let's start with what the problem is n nodes and coins we just want to distribute them that's what's true when we're given the root of this tree but when we go to a sub tree of the original tree like for example this one that's obviously not going to hold there's not necessarily going to be a match of n nodes and N coins and that is the reason this is not a simple recursive problem in my own words I don't think this is like a technical definition or anything but this is what I call it a simple recursive problem because those types of problems the sub problem is basically the exact same as the original problem whereas in this problem that is not the case the sub problem is different like this sub tree has three coins but only one node so it's very different from the original problem that had three nodes and three coins that's why this one is a little bit more difficult that's also why we're not going to try to solve it in a simple recursive way what I'm saying is the original question we're trying to answer is how many moves the minimum number of moves is it going to take for us to make sure that every single node has exactly a single coin but when I solved this recursively when I do the recursive step when I'm at this subtree I'm not asking that same question I'm not asking how many moves is it going to take for this subtree to have exactly one coin in a sense we kind of are going to do that but we're going to do a lot more than that in the recursive step that's why I'm saying that this is more difficult there's more involved than just asking this question over and over again recursively now at first glance you might have absolutely no idea what to do at this point so let's try to use our problem solving skills let's at least try to look at some examples see if we can notice any sort of patterns we know we're going to attempt to do this recursively it may or may not be possible but if it's going to be done recursively there's probably going to be a base case at some point usually with trees that means we're at a leaf node so what would that mean let's think about this for a second suppose we are at this Leaf node over here we have three coins and we know it doesn't have any children right like this is a leaf node it has three coins but it's just a single node so at the very least we know for sure it's going to take at least two moves to distribute the coins like at least at bare minimum because if this guy has three we have to send two of those to the parent that's all we know at this point right I mean I don't know how we're going to put all of this together into the solution but that's an observation like this is definitely a key observation to solve this problem let's look at the other side for a second there's obviously zero coins here but we need at least one it's a leaf node no children so at bare minimum it's going to take one move to send a coin from the parent to the child okay so we total it up and that's going to be three moves total that does happen to be the correct answer but this was a pretty trivial problem we literally only had to look at the leaf nodes what would we have done if we were at this node anyway cuz this would be the recursive step well let's take a look at this example like this is still a useful example for us to come to the solution what would we have done when we got here we know it's going to take at least two moves on this left sub tree at least one move on this right sub tree what kind of return value could we send to the parent that would be useful at first you might think it was what we just kind of talked about it was two moves on the left one move on the right and that's what we would send to the parent but is that really sufficient is the parent just going to add them together suppose we had a different example consider a slightly more interesting example over here suppose you know we get down here we have four coins that means we need three moves from here of course and we get down here zero so we need at least one move to bring a coin here so then we go up to the parent and of course we could add these moves together we're trying to do this like the naive way and we also notice well we're going to need one move to bring a coin here so plus one move from here total five moves then we go back up to the parent and we say well this guy needs one too one move there and then we just kind of add everything up and assuming we are totaling up all these mov moves and then we're returning is that enough does it really take six moves to distribute the coins in this problem I actually don't think so because look what we're not realizing when we're totaling up the moves the direction matters when we say three moves here we're moving them up and when we say one move here we're moving them down so what gets lost here is that the sign matters this is saying we have three extra coins in the left subt tree this is saying we need one more coin in the right sub tree there's a deficit of one if we move three coins over here that's three moves then we just move one coin up there and one coin down here that's five moves total but we counted six so we overcounted so now let me correct this and show you the actual way to solve it it's pretty similar to what I showed you so far we're going to say from here we have four coins but we only need one so that's plus three three extra coins from here we're going to return that up to the parent from here we need a coin so the number of extra coins I guess could be NE -1 with this information returned up to the parent now from here how do we calculate the number of extra coins that we have from here well the idea is that we can take the size of this subtree and the total number of coins we add these two together that gives us a plus two we would also add the value from here that's obviously zero so it's not going to change the total number of coins this isn't the total number of coins sorry this is the extra number of coins from here doesn't that look wrong if we have three nodes and we have four coins we don't have two extra we should have one extra so the one thing we didn't do here is subtracted one because if we introduce one more node it doesn't have any coins then we can at least take one of these extra coins and give it to this so there therefore we do a minus one here basically this is a subtree of size three we have four coins therefore we have one extra coin the number of extra coins tells us the number of moves at each step because if we have one extra coin then we're going to take that extra coin and send it to the parent okay so now we tell our parent we have one extra coin in the left sub tree which we are of course going to send to the parent and we already did that like down here in the recursive call we did that so actually at this point I'm actually going to show you the final solution cuz I think we've gone over enough of the intuition and I don't want to like confuse you more so the solution I'm about to show you is actually going to return two values from each node it's going to return the size of the tree and the number of coins in each tree now there is a way to do this with just a single return value returning the number of extra coins in each tree I think that's slightly more complicated so I'll just kind of show you that optimization when we actually code this up but I think conceptually this one is probably a little bit easier to understand so let's just roll with that base cases let's start with that over here the size of the tree let me just kind of uh denote exactly what I'm doing size of this tree over here of course is one it's a leaf node and the number of coins is of course four so obviously with this information we can calculate the number of extra coins it's all about the extra coins down here size is one number of coins is zero so obviously negative one extra coins now when we go back up here size of this sub tree we can obviously easily calculate plus one plus one and then this node itself that's going to be three the number of total coins is also pretty easy to calculate get coins from here get coins from here get coins from here add those three up we still have four going all the way back up to the parent pretty much the same thing size of this tree now is just going to be this plus one that's four and the number of coins is also going to be four the one thing I just didn't show you in all of this is how would we have actually updated our result during this whole time let's assume this is actually a global variable that's what I mean by this is not a simple recursive function like the return value isn't the result obviously so assuming it starts at zero what would we have done when we were over here we would say three extra coins right that's the Delta here so send those three coins up to the parent so we'd add three to the result when we're down here we'd say this guy needs a coin the Delta is -1 so we're going to take the absolute value of the Delta and add that to the result which is A+ one to the result and the reason for that is the number of moves is going to be a plus one to balance this because we're going to send a coin from the parent to the child and then it's going to be one and the parent is going to have two at that point this guy is going to have one at that point now from here we're going to say three nodes but four coins we should probably send one up to the parent so so now there's only going to be one remaining and the parent is also going to have a coin and so we're going to say plus one to the result over here and obviously you can see the tree has balanced all the coins basically all we did is every time we visited a node we returned this information to the parent but at the same time we asked ourselves how many moves would it take to balance this current node how many moves would it take we did that for every single node and obviously it was just a typical DFS so time complexity is going to be Big O of n space complexity is going to be Big O of n or the height of the tree let's code it up so I'm going to declare our result up here one way to do this in Python since we know we're going to actually be updating this in our recursive function which we're just going to pass in like the node in here we can't really update this unless we declare it as non local so that's what we're going to do and I think it's actually one line less of code if we declare this as like a class variable so I guess we will actually do that so in Python you can do that like this so self. result that means it belongs to the class and so now we can update it down here uh like that okay but for the actual logic of this problem starting with the base case which I guess is one thing we didn't discuss but you probably know what we're going to do if we have a null node we're going to return the size and the number of coins in this sub tree obviously the size is zero obviously the number of coins is also going to be zero so that's what we do now now we're going to run DFS recursively on the left subtree and we're going to do the same thing on the right subtree so it's kind of just a post order traversal and remember the return value is going to be the size and the number of coins I will say left size and left coins for this one and WR size and write coins for this guy now remember what we're trying to return at this point is the total size and the total number of coins how do we get that it's not too bad we we can say the size is going to be one the current node plus left size plus right size the number of coins is going to be well however many coins the current node has the number of coins in the left sub tree and the number of coins in the right subtree lastly let's not forget to actually update the result which we can do like this self. result how should we update it what do we want to add to it well basically the number of moves we need to make to give this node however many coins it needs so therefore it would just be the Delta between the size and the coins now the thing is either of these could be larger we might have extra coins or we might have too few coins it doesn't really matter to us we need to make a move either way so we're actually going to take the absolute value of this which I guess I kind of didn't show in the drawing explanation cuz in our case we had extra nodes in the leaf but if we had all the extra nodes in the root that is the case where this would be relevant you can kind of walk through that on pen and paper if you find that helpful so after that all we have to do is actually run this DFS and remember we are not returning this DFS this is not a simple recursive problem where we can just do that we're actually going to return a separate variable that we were updating in our recursive function and of course I forgot to reference this as a object variable but uh let's go ahead and run this and as you can see on the left it does work it's pretty efficient even though I think there's still the red squiggly here I don't know why that's probably just a visual bug but there is an optimization you can make that I didn't want to show you earlier cuz I didn't want to like confuse you but I think this optimization might be helpful for you to translate this into other languages so I think it's worth knowing notice that to update the result all we need to know is the number of extra coins and we're going to take the absolute value of that that's what we're doing over here so the question is instead of returning both of these things and the only reason we return both of them is so we can calculate the number of extra coins in the parent why not just return the number of extra coins that's what we're going to do and then we're going to update our math here to reflect that so first let's start with a base case if we have an empty node we assume we have zero extra coins and from the left well we're going to assume that there's only one return value from here and it's going to be the left extra I guess that's what I'll call it and from here I'm going to call it right extra with these two this is the question now knowing this we don't need to know what the size is anymore we don't need to know what the number of coins are anymore we know we're going to update the result somehow with probably just the number of extra coins that we compute and then end up returning from here now the whole question like I've changed everything about this problem to just return one value which is the number of extra coins only thing I haven't done is shown you how to calculate it maybe you want to use that as an exercise for yourself and try to figure this out yourself it's just one line of code but if not I'll go ahead and show it to you it's going to be this number of extra coins what would that be well if the left sub tree had this many extra coins and the right sub tree had that many let's at least add those together you probably knew at least this much but let's also not forget to include the coins at the current node so let's at least say okay the current node has this many coins so let's add those as well and actually had this bug originally you might think that this is correct there's just one little thing that we're missing suppose the left sub tree had zero extra coins suppose the right sub tree had zero extra coins suppose the current node has one coin then in that case we are Computing the number of extra coins for this node to be one but that doesn't seem right if the current node has one coin and like let's say the left sub tree and right sub tree are null then why would we say it has an extra coin let's put a minus one here because remember one coin is sufficient one coin is what we're looking for so we put the minus one to counteract that it does not count as an extra coin this is the entire solution and as you can see on the left it does work it's relatively efficient if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon