Find Minimum Diameter After Merging Two Trees - Leetcode 3203 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find minimum diameter after merging two trees very very difficult problem I'm definitely not going to lie about that arriving at the solution is definitely not easy but I promise you if you are at least like reasonably good at leak code because let's be honest if you're a beginner and you're jumping into a hard problem it's going to be a tough time but I honest to God think that the thought process that I walk you through for this problem is is possibly going to change the way that you think about these things so I'll try my best let's get into it we're given two undirected trees okay so a tree I know that trees are generally a cyclical and connected graphs so we have two disjoint sets in that this is like a connected component this is a connected component no Cycles what we want to do is introduce a new Edge connecting the two trees and then based on that we want to compute the diameter of the tree and so this is the key word of this problem diameter basically it means the longest path that exists in the graph or tree from any given two nodes so if we add the edge here you can see that the longest path becomes uh we can start from here here or here but it'll be the same it'll go to zero here it'll go along this Ed Edge and then here so that's a path length of three that's the diameter of this graph now we could have done it differently we could have put the edge over here and then not over here that would have been different then the longest path becomes this this this and this it's of length four now there's so many different ways to think about this problem that that's what makes it difficult so let's try to keep things simple I won't walk you through like every single thought and detail I had when I was solving this problem that might just confuse you even more but let's think first in terms of Brute Force clearly this is like some kind of graph problem probably going to need to do a graph traversal but how would we even solve it in terms of Brute Force before I even answer that question I'm thinking how the hell do I even get the diameter of a graph how do I find the longest path like even if I created this graph how would I have known how to get the diameter mainly the intuition is not that different from a leak code easy you might have solved where you are told to get the diameter of a binary tree we'll talk about that more in depth when we work on optimizing this problem but now let's just focus on the Brute Force suppose we do something like this for the resulting graph suppose we already knew what the correct graph was how would I get the diameter well well Brute Force I guess we could say for any given node we don't necessarily know which nodes the diameter is going to go through it clearly doesn't go through this node well actually I guess in this example it technically could I think this would have been the same but in any case you can imagine it wouldn't have like if we had another node here then the diameter would have gone through this and it wouldn't have gone through that so how do we do it well Brute Force for every single node compute the max path in every single Direction so in this direction the max path is one in this direction the max path is one in this direction the max path is three so now you tell me from this node itself what would the diameter be or at least rather the longest path running through this node well assuming that we can't like do something like this where we go here and then go down and then come back up and then go this way we would basically from here pick the max of the two directions so the max path length uh here I guess there's a tie so there's one here one here and then three there so we have 1 one and three what are the two biggest numbers from here it's these two thus the longest path from here is four if we do that for every single node then we can determine the diameter of the graph but how do we first of all get the correct graph it's actually not that different I think somewhat intuitively you can kind of tell by looking at the picture but I'll show you the bigger more complicated graph so here's a more complicated example and I'll tell you that the solution ution to this one is to connect this node with this node and what we're trying to do is connect this Edge such that now the diameter will be minimized so if we look at the diameter it will be this now one two and then along like this blue part and then from here we could either go this way two or this way two or this way one that's not the longest path or we could go this way in all of those cases the diameter is five we can't pick this one because that is not the longest path the diameter is by definition the longest path and what we're trying to do is minimize the diameter I know that's confusing but that's the nature of this problem now what is good about picking this node and picking this node well clearly from here the longest path in any of the directions was at most two and from here the longest path in any direction was at most two and then we put one Edge connecting both of them together that gave us a one so you just add these up and then you get five had I picked a different Edge had I picked this one and then from here I mean everything stayed the same on this side I got my two and I got my one from this Edge and from here now I have one two or I have one two or I have 1 2 3 4 wo that's pretty big so that gave us a four so we got 2 + 1 + 4 that's 7even we were trying to minimize this number but we didn't do that so based on these couple examples you tell me what's the the intuition which one of these nodes would we want to pick well this is in my opinion probably the hardest part about this problem it's very simple once you recognize it once I tell it to you you'll understand it but it's very hard to identify what we actually want to do is not necessarily go through every node and find the longest path to Any Given Edge or rather any given node from that node as a source because yes that actually would work for finding the diameter that runs through the new Edge that we just created cuz you could take that number X and then this number Y and then put a one in between them and add them all up but what if even by connecting this edge here what if the diameter doesn't actually go through this new Edge isn't that technically possible let me show you an example what if I had this I have uh this graph over here it's just two nodes connected and then I have this graph and I am going to put that there and I'm going to put that there and then here so just a very long graph it's kind of a tree just sideways and now I introduce an edge here well you could obviously say that the diameter is 1 2 3 4 five if it were to run through here but you could also say that if the diameter runs through here it's 1 2 3 4 5 6 so the diameter doesn't have to necessarily go through the new Edge that we add so what should we do because we do have to now basically get the diameter from every single node not like the literal diameter but like the longest possible path that runs through every node but haven't we solved a problem like that before haven't we solved a leak code easy like that before well I personally definitely have it's a neat code 150 problem and it happens to be a tree problem it's a third problem in the list here and so when you uh look at the solution this problem is very much burned into my mind if you don't remember it I would recommend watching this video I believe it's very short it's like a 7 minute video and I'm going to use the intuition from this problem to solve today's problem so let me uh quickly draw it out bit of a sloppy a tree over here remember this leak code easy problem where we want to find the diameter that runs through this tree it's actually a very easy problem to solve in terms of Brute Force you just go through every single node and see what's the longest path running on the right side okay it's so one what's the longest path running on the left side so 1 2 3 4 we could go this direction or we could have gone that direction but it's four in both cases so that's the longest path running through this node and we could try to do that for every single node so I'm going to do that here I'm going to see 1 2 3 1 2 3 that's 3 + 3 that's 6 this is a very easy problem to solve in terms of Brute Force it's n^2 now how do we apply that to this problem here well if I were to get the diameter or rather the longest path running through all of these nodes I can maintain that and let's say I call that my Max D no pun intended so I have that I have like the max path that runs through this graph individually and then I have the max path that runs through this graph individually and then when I want to connect them together I just have to find the longest path that runs through the new connected Edge and we can actually get that from both if I have the max path that runs through this graph the longest path is this one it's one 2 3 4 what's the longest path that runs through this graph it could be this that's two it could be this that's three nope it's this one one 2 3 4 so that's four and this is four now when we're connecting them together what do we do am I going to be dumb and put the edge like this am I really trying to create the longest path possible no I'm trying to create the smallest path possible so what I would probably do is connect them from the Midway point so since this guy is of length one I can take the Midway Point here and the Midway Point here and then connect them together and so then I can take the diameter that I had here which was four divide it by two I can take the diameter here four divide it by two yes we have to do a plus one cuz we did introduce a new Edge but the calculation is nice and easy this might not necessarily be the result as I mentioned earlier similar to like how the max path doesn't necessarily have to run through the route of like this tree we could have had like an edge over here and then an edge over here and then maybe that would have been a six which could have been the max that's why the Max D that we would have computed earlier would have been important and another tiny little tidbit is this what if we actually had something like this where it's another node over here so from like this path the max path here it's of length five so that's odd if you take five and you divide it by two what should we use well you can see by connecting this Edge still we want to take the longest path we don't take this path of two we take this path of three and so that's why you would divide by two but round up so I kind of talked about the brute force and I actually didn't even show you how we would have solved this leak code easy problem over here on the right side with the optimal solution how would we have optimized this one from n^2 to being Big O of n because the trick that we're going to use here is the exact same one we're using in this problem the unfortunate thing is that these are not binary trees these are graphs that are technically trees so the code is going to be a bit more complicated than it would have been for this one but in terms of how we would have done this one in my opinion it's easiest to do it from a DFS approach so we want to do it recursively bottom up so from here before we compute the max path that runs through here let's compute the max paths from the children so recursively we'd go to the left sub tree and then we'd keep doing that eventually you'd get to the base case and then from here you'd say well the max diameter that runs through here is obviously zero and then we would return up back up to our parent over here but how exactly would we calculate the max diameter that runs through here because what we want is the max from the left and Max from the right but do we want the max diameter from the left and the right or do we want the max like path from the left and right we want the path so that's why this problem is kind of annoying especially for elite code easy because either you have to kind of maintain like a global variable so like we could maintain like the global Max diameter outside of the scope of the function or we could do something else which is return to values so every time we return up to our parent we're going to return a pair which is the max diameter that we computed running through that given node that's just for us to be able to compute the global Max eventually by the time we get to the root if we were maintaining the max through every single node we would be able to get that Global um but also we want to know what's the max a leaf path from a given node so the max Leaf path from here from the right side we would want that guy to return up to us a one from the left side we want it to return up a zero so then we can compute running through this node here it's going to be 0 + 1 that's going to be the diameter so that's going to be the idea when we uh solve this as well so we're going to take that algorithm here so like for example here if I had the max Leaf path from the left side it would return to me up a three and I'd do the same thing from the right side it would return a three I'd add them both up I'd say the diameter running through here is going to be six but that's not what I'm going to return up to my parent yes I'm going to return six but I'm also going to return the max Leaf path which is going to be the max of either the left side and the right side they're both the same this time so that's three and I'd add a plus one because I know that there is one more Edge connecting me to my parent and by the way if like this was a two for example we would have taken still the max of these two which would have been a three that tells my parent that there is a path on the left side that is of length four when you take this out and you apply it to this problem we know that this is a tree we could pick any given node as the root of the tree so I'm just going to start at zero and I'm going to say okay the max Leaf path well I wouldn't compute the max Leaf path I'd compute the max diameter but I'd be doing both at the same time recursively it's more difficult obviously here since it's not a binary tree so imagine something like this where I have a tree like this and I have three children actually one of them has a child and then this guy maybe has two Childs so how would I solve it now on a general tree looking like this it's pretty similar I'm going to recursively go to my left side here get the diameter going through here obviously it's zero okay well what's the path from here well that's going to be one and then same thing down here I'm going to get the path that's going to be two I'm going to get the path over here that's going to be three so now I have all of these paths I can choose any direction what is the diameter running through this node we can only pick two paths which of these two paths are we going to pick the two biggest ones so this guy and this guy that's going to be a 2 + 3 and then we'll say the diameter running through the root is five so in summary what we're going to do is obviously run that diameter function on this graph and this graph and so that will give us something let's say I I get D1 here I get D2 here so the result could either be this or this or it's going to be this divided by two taking the ceiling of it and this divided by two taking the ceiling of it and then adding a plus one to actually connect these two together among those three values that is what the result is going to be since we're just running a graph traversal on each graph a single time the time complexity is going to be n+ M where these are the sizes of the graphs respectively let's code it up I will go ahead and reset this I didn't mention it at the beginning of the problem but like the number of edges in each graph is going to be one less than the number of nodes since each of them is a connected graph with no cycles that is technically implied so we can say that the length of edges 1 plus one is the number of nodes in that graph and then we can just copy this and then make it similar over here for the second graph as well for each of these we're just given the edges we want to build an adjacency list so we can actually Traverse each graph uh I could write the code for that but I think it's probably better to put it into a function so we don't have duplicates so let's create a build adjacency list given some edges I'll make it a a default dict so it's easier to work with returning that and then going through each pair of nodes just like this and since they're undirected edges we can make them go both ways so just like that and then swapping these now that I have that I can get my adjacency list for each graph I'll pass an edges one here and then I'll just copy and paste this for the second graph you can see there's a lot of repetitive code that is another challenge about this problem what I need is just one function that can get me the diameter from a given graph and I'm probably going to implement this with DFS so if I had that how would I be able to solve the problem I'd be able to do this give me the diameter one from the first graph so I'd pass in uh adjacency list one and then I'll copy and paste this and then uh D2 is going to be this adjacency list 2 and if I had that this is how I would solve the problem I would return the max among three values either it's going to be D1 that's the longest diameter or D2 or it's maybe running through both of the graphs in which case I can say ceiling of D1 / 2 plus ceiling of D2 / 2 and then a plus one to actually connect them together so maybe I'll put the plus one at the beginning just so you don't actually miss that when you're reading over this code this is how to solve the problem it's not easy and the hardest part is kind of still left over but I would say that this function implementing this function here is probably a leak code medium it's not insanely hard as I say that I hope I don't actually mess it up or anything so from here we're going to be returning two values we're going to return the diameter that runs through each given node and the max Leaf path remembering these two things makes it easier so we'll be given a current node and since we are running this function on two different graphs it makes it harder to have a global outside of here like outside of here we could say Max diameter right and then inside of here we could use that variable by calling it non-local so we can reference it out there and then maybe after we were to call the function we could then just save Max diameter in D1 for example so that we don't overwrite it and then we could call a get diameter again passing in the second graph and then we could say D2 is equal to Max diameter which is the variable we declared out there I feel like that's more messy it's easier to do it this way where we actually have the return value of the function be the diameter so we don't have to worry about globals and stuff the fact that we're running the function twice is what makes it difficult so my Approach is going to be this I will be given the current node I will be passing in an adjacency list even though the graph is a cyclical the way we're going to Traverse the graph is like this I'm going to go through every neighbor in the adjacency list of the current node I might end up going back to my parent I don't want to do that so I can pass in the parent as a parameter as well so when I'm calling the get diameter here I will call it like this let's start at zero let's pass in negative one for my parent because this guy doesn't have a parent yet and then adjacency list one I'll do the same thing for the second call here let's also recognize that this get diameter is returning two values now the second one we're not going to use we don't actually care about the max Leaf path after we return so I'm going to call that the underscore it's an unused variable same thing here so now remember what we're trying to do here we're trying to get the max diameter I'm going to call that Max D that's going to be one of the values we return in our pair Max D what's the second one it's the max Leaf path how do I get that I get that by maintaining the two Max child paths let's initially say they're both zero and if I had the two Max child paths I can get the max Leaf path by taking the max of those to Max of Max child paths and then add one to it so one plus that because remember the max Leaf path is what we're trying to return up to our parent so even a leaf node would return one even though a leaf node will not have any children it should return one okay now for this part it's not too bad but you do want to be careful to not make a mistake so I'm going to say for every neighbor I want to run DFS I want to run the get diameter function on the that node on my neighbor and for the parent I'm going to pass in the current node so that we don't end up in a cycle and I'll pass in the adjacency list now who knows the neighbor could have been our parent so before we actually execute this let's guard it with this if neighbor is equal to parent then just continue to the next iteration of the loop don't do anything down here otherwise we call this we get two return values we get the neighbors diameter and we get the neighbors Max Leaf path I know these are long variables uh name but I think it's probably worth doing them so we want to maintain what the global like Max diameter was so with the neighbors diameter we can possibly update that so max diameter is equal to Max of itself and the neighbor's diameter now you're probably thinking well how do we use the neighbors Max Leaf path to maintain the two longest leaf paths there's many ways to do it probably some if statements you could maybe sort the array and do all sorts of stuff I think the easiest way is just to treat it as if this is a heap of Max like a capacity of two so what we're going to do here is say Heap push usually I say Heap q. Heap push but I guess nowadays the leak code Imports don't even require you to do that so we can do it this way Heap push onto this even though this is not a heap right now it doesn't really matter since all the values are the same it technically is in the form of a heap so we can say Heap push Max child paths and push the value here that we just got that Max Leaf path so push push it and we don't necessarily know that that is among the two largest paths so let's pop the smallest one that is there now this is of size three now so let's pop the smallest one so the two largest remain so we'll say keep pop from Max child paths okay you might think that that's pretty much the entire solution we're almost there there's just one little thing we're missing we're trying to return the global diameter the max of it and the max Leaf path we definitely have the max leaf hats that was easy enough what about the max diameter we only got the diameters running through the children we actually never computed the diameter running through the current node the whole reason or at least part of the reason we were getting the two largest leaf paths was so we could compute the diameter running through the current node how would we do that just like this take the sum of them isn't that pretty easy I think so so just say sum of Max child paths but how do we know if that's the maximum well we can just update the max diameter like this so try to clean this up Max diameter is equal to Max of itself and this particular sum so there you go a lot of code a lot of complicated stuff going on here but I think if I can zoom out all the way well it's kind of hard too but you can see it is 36 lines of code most of the complicated part is here let me give this a run of course we always have a typo I have three PS in a row here apologies for that uh but now you can see that this works and it's pretty efficient I know that it looks like it's less efficient than the others I'm not 100% sure the reason for that if I had to guess I would think it's probably related to the Heap because I think in terms of Big O time complexity this is definitely optimal or maybe I think there are a couple other traversals we could have done on the graph it's possible that doing the BFS solution it doesn't have the overhead that the recursive solution does but I think that this is probably the simplest solution at least in my opinion to this problem and I really doubt that this stuff matters in an interview if you found this helpful definitely check out N.O this one definitely took a lot of work but I had fun with it nonetheless see you soon