Microsoft Coding Interview Question and Answer: Lowest Common Ancestor

Key Takeaways

in this video I'm going to discuss a Microsoft interview question and answer and this problem is called the lowest common ancestor problem so let's just dive into it here's the problem we have a tree as you can see on the left and we're given two elements four and five and we're trying to find the common ancestor that's the lowest in level in this case the answer would be three because we have two common ancestors for these two elements one and three and obviously three is the lower one of them and the LCA the lowest common ancestor of three and five three and five would be three again so LCA could be one of the given elements and the LCA of four and two four and two would be one and then L CA of 6 and six the same element would be this element itself so how can we solve this problem if you want to try solving this problem yourself pause the video right here and see if you can come up with the solution and come back to the video later there's a number of solutions to this problem but the one I find the simplest is the following let's say we're trying to find the LCA the lowest common answer of four and five what I would do first is I would find the path from the RO to one of the elements four let's say I do that by going to the left and then left again and right there I find the element so the pass to that element would be 1 14 134 and I would do the same thing with five so I start at the root again 1 three to the left and five is not there so I go to the right left again and I find the PATH so that's 1 3 65 and by examining these two paths 134 and 1365 we see that these two paths are the same up until three and converge or diverge after that so in these two paths we can see these two elements are the same so we return the last element in this common pass as the LCA of these two elements now the key to implementing this solution is this function pass to X it takes the root and the element that we're looking for X or five in this case and it returns a stack of this path or it returns this this path as a stack so it would look like this 1 3 6 five I'm just going to write it as a list for now and then same thing for this one four so the path is 134 so I'm going to write 134 right here and given these two paths we're able to to look at each element at a time and see which ones are the same until we find different elements six and four and we stop right here and we can just return this element as the LCA now if you want to try implementing this solution yourself pause the video right here and come back to it later when you're done here's my implementation to our solution and in particular the PA to X function let's say as an example we are trying to find the path from Rue to five this element and we have a recursive solution here if the element or the root that we're looking at right now is null then we just return no and if we're looking at the element that we were just looking for if root do value is equal to this one then we create a stack with this element alone and then we return that and let's say we're looking at this element now and if the left pass or if the left child contains a pass to X then that means left path is going to be not null and so we return left pass after adding the current element that we're looking at this one to the left pass and then we return that and we do the same thing with the right pass if the right pass let's say we're looking at this element If the righted child contains a pass to X or five in this case then we add the current value to the right pass and then we return that if neither children contain a pass to the element that we're looking for if we're looking at this element say then we just return no now using the code that we just implemented let's just Implement our main function LCA that takes root and the two elements and let's call them J and K and in particular we'll be looking at this example of the LCA of four and five now the first first thing we do is we find the paths to J and K or four and five which would be these two and then we initialize LCA to return as not or anything else and while pass to J and pass to K are non empty we pop these two stacks or these two paths and call them Jpop and K-pop and popping just means we take the first element and if these two elements JP and KP are the same element then we update LCA to return to that element so LCA to return becomes one and then three because these two elements are still the same and then we stop right here when these two elements J pop and KP are not equal and break and we return LCA to return in this case three as the LCA and that's it for the video thank you so much