Maximum Width of Binary Tree - Leetcode 662 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum width of a binary tree we're given the root of a binary tree and we want to return its maximum width well what is its maximum width well it's a bit different than what you might expect taking a look at this binary tree this level has a width of one because there's just a single node in that level the second level has a width of two there's two nodes in this level the third level here does not have a width of three like you might expect it has a width of four basically it's measured as taking the leftmost non-null node in the level and the right most non-null node in the level and getting the distance between them and in this case the distance is measured by each spot where a node could go like here there is a node but we know that there could also be a node over here so that makes this distance of length four so even though there's three nodes we say that the width of this level is four so that makes it a bit trickier than you would think by just using like a simple algorithm like breadth first search because with tree problems those are usually our two choices we can either do DFS depth first search or BFS breadth first search in this case since we are trying to get the width of a level BFS does seem more intuitive but it's also not quite as straightforward as you might think because with breadth first search the answer that this would give us for the third level here is three but we would actually want a four now otherwise breadth first search is pretty good because what it will do is it will go level by level allowing us to get the width of each level because we don't necessarily know that the last level will have the widest width so we have to do so for each level but the question is how do we count these empty positions let's take the same tree structure as this example you might first try taking this node and adding it to a level okay then add its children to the next level and then take these two nodes and start adding their children to the next level let's say that this fourth level is the one we're paying attention to right now here since we want to be able to count one two three four let's try adding null to the queue so even though this guy's left child does not exist we can try adding that to the queue as well as well as adding this real one then when we start popping from the queue we'll count one two three four and it'll give us the accurate count now the problem here is if this guy doesn't have a child then this guy will also not have children either but for the subsequent levels we do want to get the accurate count so this is a method like we technically could do for null we could also add null to the queue for its children but this is going to get complicated and a pain to code up but we can use a similar technique here to count these null nodes and the idea is reminiscent of how heaps work with a heap data structure each node is actually numbered starting at one and the number assigned to its left child is always two times what its value is so the left child is going to be two and the right child is going to be 2 times that plus one so it's going to be 3 here and this guy's left child is going to be 2 times 2 which is 4 and I'll just quickly fill in the rest of this structure the right child here is going to be 2 times 2 plus 1 that's 5 left child here is going to be six right child is going to be plus one seven and we could continue building out the tree structure just like this but how does this help us well ideally we would be able to assign each node in the tree a value corresponding to its position then even if a node like this one doesn't exist here we will still count the width of this level as being 7 then the value assigned to the rightmost node and four the value assigned to the leftmost node will take 7 minus four that's three we'll always do a plus one because that's just how calculating the length works so now our result will end up being 4 for this last level so that's the idea now how exactly are we going to implement it using breadth first search well it's pretty simple we're gonna have our Q data structure we're going to add the root to the queue which is one we're also going to assign this node a number and the root is always going to be starting at Value one so this is going to get confusing because we have multiple numbers but I'll just show you the first one is going to be the node the second one is going to be the number assigned to that node and the third one is going to be the level for that node in this case for level I'll just say it's starting at zero though we could say this is the first level the level doesn't really matter but it's going to be used for us to distinguish when we're at this level and then we move to a another level so let's say the level is zero then when we pop from our queue we get its two children and add those to the queue so we would add three to the queue and we would add two to the Q I'm just putting the values themselves just assume we're also adding the number and the level but for this node its number would be two and this guy's number would be three even though that's like the opposite of like their actual values but you can see getting the number of a node is as easy as just incrementing if this guy starts at one this is going to be two this is going to be three four five six pretty simple to get the number and the level is also going to be pretty easy because when we take the children of this guy an appendum to the cube we're also going to say well if this is level is one this is level is going to be plus one so it's going to be two or wherever we start at if this was zero this would be one and lastly to actually get the width of a love level anytime we get to a node that is the first node in that level we will know because we have just popped it from the queue and its level is different than the previous one so we'll be able to automatically detect that and we will always know the first node in a level so then when we get to every other node we will easily be able to calculate the width because we only need the first node in the level and whatever the last node in the level is to calculate the width since this is just a BFS algorithm we are going to code this up in Big O of n time where n is the size of the tree same with memory complexity so now let's code it up so the first thing I'm going to do is initialize our result and I'm going to set it to zero and then we are going to get started with our Q in Python it's called a deck so we can initialize it like this and what I'm going to do is pass in our first Tuple which is going to contain the root node as well as one is going to be the number assigned to it and 0 is going to be its level so I'll add a comment just to make it more clear now while the queue is non-empty we are going to want to pop from the queue so we're going to say Q pop left we get three values the node the number of the node and the level of the node now how do we update the result if we wanted to well we would want to set the result equal to the max because we are trying to find the maximum width we would take the max of itself and we would calculate the new width how do we do that though remember I was talking about taking the number of the current node and subtracting it from the first node in the same level so we have to keep track of the level how do we even update the level well if we ever got to the point where the current level was greater than the previous level then we would set the previous level equal to the current level the current level wouldn't really change because it's going to be updated on each iteration of the loop well first of all we're going to need a new variable for this so I'm going to do that over here we're going to keep track of what the previous level is and we're going to keep track of what the previous number is this actually should be called the number of the first node in the current level because that's what it's going to be used as I'm going to initialize both of these uh well the level will say is going to be zero to start out with and the previous number I guess is also going to be zero it should be one less than whatever our first node's number is for the math to work out but here where we are updating our previous level let's also set our previous number equal to the current number so this means anytime we update our level the number the previous number will always be set to the first nodes number in that level that's exactly what we want because now when we calculate the width of the current level we can say the current number minus the previous number plus one this is our offset that we're always going to include and there we have it we have updated our result the only thing you don't want to forget is for the node we also have to add its children to the queue but we're only going to add the children if they are non-null so I'm going to check is the left node non-null if it is then we are going to append it to the queue as like a sub list or a little list with three values the child itself node dot left as well as the number of the node the left child is always going to be two times the current number and the level which is always going to be plus one of the current level since this is a child of the current node its level of course has to be plus one and we're going to do the same thing pretty much for the right child as well the one thing I will mention though is make sure you append the left node before you append the right node because remember with cues it's first in first out we are trying to go left 2 right here so this will be right this will be right and the number is always going to be 2 times num plus 1 and the level is also going to be level plus one so that is pretty much the entire code let's make sure we return our result and let's run this to make sure that it works okay it looks like we just missed an edge case which I think is good because this is an opportunity to actually go through the code really quickly and show you where I had a small bug so here we can see that the code worked for 74 cases but on the 75th one we failed and it's definitely an edge case because we're given a tree of size 1 where this is the root node just a single one and we were expecting an output of one which makes sense the width of a single node tree should be one but I returned true why is that the case well it's because we gave the root node a number of one but we gave the previous number a value of zero this Loop will only execute once where the current node's number will be 1 the previous node's number will be zero and the width we're going to end up calculating is two so the way to fix that is going to be to give the previous number an initial value of one so that if we ever calculate the width of the first level we will get a width of one so let's rerun that to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neatcode.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon