Minimum Height Trees - Leetcode 310 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum height trees we're given a graph that is going to be connected but it's not going to have any Cycles within it so by definition it is going to be a tree and this graph is going to consist of n nodes labeled from 0 to n minus one and we're going to have exactly nus1 edges and that's a very special number if you are familiar with graphs because for us two have n nodes and have them all be connected and not have any Cycles we are pretty much required to have exactly nus one unique edges cuz if you look at this graph over here if I were to add a fourth Edge then I would be introducing a cycle no matter what and also if I were to remove any of the edges I would be disconnecting the graph regardless of which Edge I remove so that's a special number um But continuing if we were to pick any of these nodes as the roots which you can see that they've pretty much done here so this is the graph that we were given four nodes and these are the edges consider if zero was the root of the tree well the height of the tree would then be two if one was the root of the tree the height would be one if two was the root of the tree the height would again be two same thing over here the height would be two so among all of those we want to return the root such that the height is minimized this was two this was one this was two and this was two so this one is the only one that minimized the height therefore we return a list with one inside of it just based on that alone it's not too difficult to at least conceptually arrive at The Brute Force solution and that would be doing a graph traversal whether it is DFS or BFS and basically like they did with this picture consider every single node at as the root figure out what the height of the tree would be then with BFS we'd kind of do it layer by layer so here the height is one and here the height is two so that's how we would do it we could also do DFS and then figure out okay the path here was two the path here was also two so we would take the maximum of whatever the paths are and we'd get two we would do that for every single starting point and then among all of those we'd figure out which was the minimum the minimum was one and only a single root gave us that height so then we'd return that now the problem with this Brute Force approach is it's not very efficient what do you think the time complexity is well if we have n nodes that means we have n starting points we're going to run this graph traversal regardless of which one we choose we're going to run it n times on this graph doing this graph traversal is going to require us to visit pretty much the entire graph so therefore the time complexity here is going to be Big O of n squ where n is the number of nodes now typically in a graph the traversal is going to be the number of edges plus the number of vertices but remember the number of edges here is pretty much proportionate or equal to the number of nodes so we don't really have to consider that in terms of the time complexity so we just can say n^2 okay that's for The Brute Force but how can we make this more efficient I will admit this is a pretty hard problem for a medium graph problem so don't feel too bad if you weren't able to figure it out by yourself so there 's actually two solutions for this problem I'm going to end up coding the one that I think is easier to code up but that's kind of subjective so I'll at least conceptually explain both of the solutions before we even do that let's just consider how would the height be minimized suppose we just have a single node okay that's simple enough this is going to be the root now if we introduce two nodes I guess both of them are the root right that minimizes the height if this is the root then the height is going to be one if this is the root the height is also going to be one kind of looks like a face but okay let's ignore that let's make it more interesting let's add a third node and let's do it like in a straight line cuz regardless of where we add it it's going to be a straight line anyway but now we see the length of this entire thing is two so if this were to be the root the height would be two if this is the root the height is also two but here it's special the height is going to be one so this would be the root Ro of the tree now we can get more interesting now we can start adding nodes either here or here or here we have three choices of where we add nodes and that's because we have three nodes any node can be used to add a neighbor to that node so even though we're thinking about this in terms of trees ultimately this is still a graph so I think it's useful to think about it in terms of neighbors rather than children so what happens now if we add a node here what exactly did we do let's just look at it for a second remember the height of this guy over here is two if we add a node here we're kind of increasing the height to three over here the height was one because we go that way or we go this way but by adding a node here we're increasing the height to be two also from the perspective of this node the height actually doesn't change because the height here was two and if we add a node here the height in that direction is one so we would take the maximum and two is going to end up being the height from here okay so in that case a node here that would mean that these two are the roots of the minimum height trees because both of them had a height of two so we're just playing around with this so far just trying to build a little bit of intuition now let's try to consider this case we could add a Noe here but that'd be pretty much the exact same as I just showed you except on the other side but let's try it here in the middle this is special because the height of the tree does not change and that's going to be true if I add another one here and another one here and another one here and now it starts to get a little bit intuitive what we're doing this is not changing the height I could add a million nodes and I'm not changing the height but if I now add a node here just like we did before just like we did with that thing it's going to increase the height before I do that we still have a single root node and the height of course is going to be one if we consider any of these as the roots the height is going to be two this way or this way or the other way right but now when I add a node here this is still the root because the height is now two it's been minimized this is not going to be the root its height is going to be 1 2 3 but this one is also the root now because look distance here is one okay but distance here is two minimum is two okay so now we have two Roots just like we did before but what about all the other nodes here are they also Roots let's just quickly check well for this one 1 2 3 so nope it does not have a height of two it has a height of three it cannot be the root and just because of symmetry the rest of these are also kind of ruled out but intuitively what we kind of learned is these outer layers are indicative of something perhaps instead of going from the middle and going out we can go from the out and go in to the middle this is the first solution I want to show you and it is relatively simple to code up in my opinion because what we do here is we notice just observationally what is different about these nodes and this node and even this node compared to these two nodes well it's the number of edges I mean of course this one has a ton of edges but this one has two edges in two directions but all the rest of these just have a single edge therefore in terms of a tree they can be considered leaves this is where we start we identify these outermost nodes and we do so based on the number of edges the nodes have these ones only have a single edge of course every node in the graph is going to have at least one Edge because it is a connected graph but not every node is going to have exactly one Edge we start with these nodes and what we do is we rule them out we know that the outermost nodes cannot be the root of the tree just like if you think about it in terms of like a straight line like this of course the outer the end points cannot be the middle of the list in a sense we're looking for the middle of this graph now we've done done that and now we have two nodes remaining now we could do it again we could rule out these two nodes but then we'd be left with nothing so what we say is since we have these two remaining this is our result and just to kind of rewind a little bit the reason we'd be able to identify these two middle nodes what we would say is as we went through every outer node we're going to kind of chop off the edge so for this node we would get rid of this Edge so it originally had two edges connected to it now it's only going to have one this node had one 2 3 4 5 6 seven edges connected to it but we took out one 2 3 four five and six boom boom boom boom boom and boom boom so we took six and now there's only going to be one Edge connected to this and it would be the one right over here on the right at this point our graph is pretty symmetrical and so we would return this as the result this brings me to a important point which is that even though they tell us to return a list of the roots that minimize the height of the trees there's only going to be at most two roots that do that there might only be one root or there might be two Roots there's never going to be more than two Roots I won't like go super in depth into why but I think it's somewhat intuitive when you kind of draw it out and just think about the examples think about if we have just a single node remaining of course that's going to be the root that minimizes the tree if we have two nodes remaining well both of them kind of minimize it it's symmetrical right now if we have three nodes this is the only way to draw it like I mean I could technically draw it like this but it's still a straight line isn't it so with three nodes they can't all be the root of the tree it's just not possible so we'd have to remove these two and then we'd be left with one and the same thing when you have four nodes whether it's like this or you draw them in a line you're going to end up minimizing it to either two nodes remaining or one node remaining if you get rid of it like this so I think this is a really key observation to make to be able to solve this problem efficiently that there's only going to be atmost two roots of the tree there are many lines of logic that will help you arrive at this so this is the solution I am going to code up so if you want to see the code for this you can skip to that but I also wanted to quickly show you a slightly different way to solve the problem at least conceptually I won't explain the intuition of this approach too much but I'll quickly walk through it and then explain why it works a little bit after that so the idea is we pick any node I won't pick the middle node just to kind of make it more interesting I'll pick a random one over here we pick any node and what we say is we run DFS or a BFS we try to find the longest path starting from this node it could go here or here but interestingly enough it's going to take us to this node over here the distance of this path if you just count like the edges is going to be three 1 2 3 once we do that the node that we arrive at is going to be a special node and the reason for that is because we know with 100% certainty that this node is going to be included in the longest path in this graph globally when we started here we don't necessarily know that this node is going to be included in the longest path but we know for sure that the node that we arrive at is going to be for sure cuz we picked this one randomly remember we just picked it arbitrarily we just chose it and a little bit of the intuition here what if I added another node over here right now this is obvious right like this took us here and it's kind of obvious that this is included in the longest path which by the way is going to be any of the it could be this is of length three it's also this it's also this but if I add a node here now it's more interesting if I start here I can take this path it's of length three and I can also take this path it's of length three so which one do we pick it doesn't matter cuz both of these are the longest path starting from here and so by saying that we guarantee that both of these nodes would be included in the longest global path so regardless of whether we arrive at this one or we pick this one Watch What Happens we are trying to find the longest path now starting from here and it's going to be 1 2 3 4 if we started from here it'd be the same thing 1 2 3 4 and at this point it would be similar to the solution I showed previously so once we pick one of the nodes and we guarantee that this is included in the longest path now we want to find the longest path and it's going to be this of length four because remember all the other paths are of length three so this one is special it's of length four now we basically start at the end points and then move towards the middle so get rid of this okay now we go here and here get rid of these and now we are here so along that path it had five nodes in it and we chose the middle one over here and that is the root that uh minimizes the height of the tree it makes sense why you'd want to go in the middle doesn't it because that's how we would minimize it if we were were not going in the middle it'd be kind of a lopsided tree like these for example whereas this minimizes it it keeps it even and just to convince you even more that this approach Works let's see what would happen if we actually made a three-way tie so we add another node over here so now this could either go there or it could go there or it could go there there's three choices well it doesn't matter because even though now there are multiple longest paths this one of length four this one of length four and this one of length four notice how all of them converge at the middle so this is the intuition of this approach if you were to code it up you'd basically run either DFS twice or BFS twice and your goal would basically be to find one of these longest paths so whether it's like this one for example you'd get this path you'd have a starting point in an ending point and then you'd basically get the middle whether it's one node or it is two nodes in the middle so if you got got rid of this it'd be these two nodes then you'd return those nodes but that's more complicated in my opinion to code up so I'm going to stick with the first approach I showed you the first thing after all that complicated stuff we're actually going to start with something easy we're going to build a adjacency list for the input that we're given because we're just given the pairs of edges like each Edge is just connecting two nodes but we want to be able to map a node to all of its neighbors cuz that's going to be pretty important so we're going to create a default dictionary of list and we're going to go through every Edge so node one node two in the edges so we're just unpacking the pair we're going to say for neighbor or for node one let's append its neighbor node two and do the same thing in the opposite direction so node two has neighbor one now is where we kind of count the edges for every single node if you're familiar with topological sort this is similar to that algorithm at least this is one variation we're going to count the number of edges we're going to do that in a map so we're going to say for every single node we want to count its edges how do we do that it's actually pretty simple cuz we created an adjacency list which we're going to need later in the problem but it's also going to be useful here so for every node let's say Source Neighbors in the adjacency list and we can unpack the items like this we're going to say that if the number of neighbors that this node has is equal to one then that means it's a leaf node it's something special and so we're actually going to declare a separate variable for that we're not going to just make it a list we're actually going to make it a q in Python you can do that like this this part won't be super complicated you'll see why I did this when we continue the rest of the algorithm but if you wanted to you could leave it as a list for now but I think it's pretty clear why we want to start with the leaf nodes because we're going to go layer by layer into the middle of the graph slash tree just like this if they have a single neighbor then they must be leaves so we'll say leaves. append The Source regardless of whether it's a leaf or not we do want to count the number of edges for every single node so we'll say Edge count for this is going to be length of its neighbors great now is where we basically go layer by layer this is why we had a q here because while our Q is nonempty we are going to go layer by layer so we're going to go through an individual layer like this for I in range length of leaves just so you know in Python this is the equivalent of doing this taking a snapshot of the number of leaves here and then doing this so in most languages this is not the case but in Python this is equivalent to what I had here and the reason for that is because range is actually a function it's only going to be called a single time so whatever value we pass into it is what this is going to end up being and then we'll enumerate that many times the reason that's important is because inside of this Loop we are actually going to be modifying the leaves Q we're going to be adding to it and removing from it so we want to take a snapshot of the length before we execute this Loop so now we pick a node in the outermost layer and we pop it we say leaves. pop left and we get the node and then we will go through the neighbors of that node why are we doing that because we want to update the edge count remember we want to now identify the new nodes that are on the outermost layer for us to do that we say that okay if this outermost node or this node has been removed then its neighbor must have lost an edge so we can say this Edge count of the neighbor go goes down by one and the very convenient thing is only the nodes that lost a neighbor have a chance of becoming leaves so we don't have to brute force it we don't have to go through every single node in Edge count all we have to do is say if a node lost an edge right now let's just check is The Edge count now equal to one if it is then we know it has become a leaf so what we would say is leaves. append WR the neighbor maybe it's still greater than one that would be fine we would just skip this part this is kind of the core part of the algorithm the only thing we're missing here is the terminating condition when do we return how do we return how do we know we can stop well we're probably never going to go until this is empty because then we'd be left with an empty graph right one thing we want to do is keep track of how many nodes we have left like how many nodes that we haven't visited in the adjacency list that we haven't removed from a layer so we're going to have we're going to conveniently use the variable that they gave us n is the number of nodes we started with every time we pop from the Q let's just decrement n by one we know we can stop when we're out a layer we're at a layer here and N is less than or equal to two that means the total number of nodes is less than or equal to two the total number of nodes remaining not the total number of nodes in leave that would be the outermost layer it could be possible that the outermost layer has one or two nodes but the total number of nodes is still greater than that so we want n to be less than or equal to two if that's the case what do we do well we can return whatever the remaining nodes happen to be and they are going to be in leaves that's a CU though so we can convert it to a list in Python just like this and this is the entire code so it's not you know super crazy nothing super complicated that we're doing here just building an adjacency list the in degree of every single node the number of neighbors every single node has and then running a relatively simple bread for search in my opinion probably the hardest part of this is just knowing that there's going to be less than or equal to two nodes there's going to be only two nodes that are the minimum height trees okay a very very sloppy mistake on my part I apologize so here we're checking if Edge count is equal to one I don't know why I did that I pretty much just forgot to put the neighbor here we want the edge count of that neighbor and checking if it's equal to one so now let's run the code and this is actually a good bug and I'm kind of glad I did this live so just to show you that it's not magic so we actually missed an edge case it's the last case here that tells me maybe leak code actually missed it the first time that they created this problem and then only added it later but can you recognize why we missed this so if n is equal to 1 and we have no edges which is going to be required if we have exactly one node then we're going to have zero edges and we return turn an empty list but the expected output is actually this I think our solution actually never really returns because this Loop would not execute this would then not execute either and then of course leaves would be empty so this would not execute either so that's a problem and that's only going to happen if we have zero edges and if we have zero edges then we must have one node so the easiest way to check for this is just add an if statement if and is equal to 1 then return an array with the value zero why do we return the value zero because remember the nodes are numbered from 0 to n minus one you also could just check if edges is empty like this but they are actually equivalent because we know we're always going to have exactly one more node than we have edges so let's take this code and run it now you can see we pass and it's a relatively efficient solution if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon