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 4 & 5 and we're
trying to find the common ancestor
that's the lowest in level in this case
the answer would be 3 because we have
two common ancestors for these two
elements 1 & 3 and obviously 3 is the
lower one of them and the LCA the lowest
common ancestor of 3 & 5 3 & 5 would be
3 again so LCA could be one of the given
elements and the LCA of 4 + 2 4 & 2
would be 1 and then LCA of 6 & 6 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 a 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 ancestor of 4
& 5 what I would do first is I would
find the path from the root to one of
the elements for let's say I do that by
going to the left and then left again
and right there I find the element so
the path to that element would be 1 4 1
3 4 and I would do the same thing with 5
so I started to route again 1 3 to the
left and 5 is not there so I go to the
right left again and I find the path so
that's 1 3 6 5
and by examining these two paths one
three four and one three six five we see
that these two paths are the same upon
to3 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 path as
the LCA of these two elements now the
key to implementing this solution is
this function pass to X it takes the
route and the element that we are
looking for X or 5 in this case
and it returns a stack of this path or
it returns this path as a stack so it
would look like this 1 3 6 5 I'm just
going to write it as a list for now and
then same thing for this one for so the
path is 1 3 4 so I'm going to write 1 3
4 right here and given these two paths
we're able to look at each element at a
time and see which ones are the same
until we find different elements 6 & 4
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 path
to X function let's say as an example we
are trying to find the path from mu to 5
this element and we have a recursive
solution here if the element or the
route that we're looking at right now is
now then we just return
and if we're looking at the element that
we were just looking for if booth 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 path or if the left child contains
a path to X then that means left path is
going to be not now and so we return
left path after adding the current
element that we're looking at this one
to the left path and then we return that
and we do the same thing with the right
path it's the right path let's say we're
looking at this element if the right
child contains the past 2x or 5 in this
case then we add the current value to
the right path and then we return that
if neither children contain a path to
the element that we're looking for if
you'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 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 now or
anything else
and while pastor J and pass to K are
non-empty we pop these two stacks or
these two paths and call them j-pop and
kpop and popping just means we take the
first element and if these two elements
j-pop and kpop are the same element then
we update LCA to return to that element
so LCA to return becomes one and then in
three because these two elements are
still the same and then we stop right
here when these two elements j-pop and
kpop 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