Hello friends my name is Tushar and today I'm going to talk about how to
find lowest common ancestor in a binary tree. Again we're talking about a binary
tree not a binary search tree.
So, for example this is the binary tree I have and I've two nodes,so for
example 2 and 8,then what is the lowest common ancestor of 2 and 8.So 2 is here,8 is
here
so the lowest common ancestor of 2 and 8 is 3. So basically we're looking at a
point, we're looking at a node from which the path diverge for the two nodes.
Taking another example lowest common ancestor of 2 and 5,2 and 5 is 6 because from 6 they
diverge in 2 different directions.
Similarly lowest common ancestor of 9 and 5, 9 and 5 is 11.
Also lowest common ancestor of 8 and 7, so 8 and 7 is 8
because 8 is the ancestor of 7 so 8 also becomes the lowest common
ancestor of 8 and 7.
Similarly 9 and 3,9 and 3,the lowest common ancestor is 3. So how do we solve it?
There are multiple ways to solve this.One solution is to traverse the path from
root till the 2 nodes and see what are the common nodes between them.
So for example between 2 and 5
the,the path from root till 2 is 3,6 and 2 and the path from root till 5 is 3
6,11 and 5.
So what happens is we keep checking till the point which,at which this path gets
different. So 3 and 3 is same,6 and 6 is same,2 and 11 is not same.It means that 6 is
going to be the
lowest common ancestor of 2 and 5 and
6 is the lowest common ancestor.The problem with this approach is that it needs
extra space.
So next we're gonna look at the algorithm which does this, finds the lowest common
ancestor in linear time and it does not take extra space. So the algorithm is as
follows.
You search for either of the two nodes whose lowest common ancestor we are looking
for starting from the root node.Any time any of the node is found we return
that node to it's parent in the binary tree.
Any time any node gets a not null node from the left side and a not null node from
the right side it knows that it is the lowest common ancestor and then it returns
it's node value to it's parent. Let me explain this with the help of example.
So here we have, we're looking for lowest common ancestor of 2 and 5,so 2 and 5.So
starting from 3
we check is, check if 3 is either 2 or 5.So node 3 is not same as node 2
or not same as node 5.
So then we expand our search,we go on the left side. We check that is 6
same as 2 or 5. 6 is not same as 2 or 5, so we go on the left side again.
So we check is 2 same as 2 or 5. So 2 is same as 2
so from this point we are going to return the node
2. Then from the 6 we're going to go and search on the right side.
So again 11 is not same as 2 or 5 so then we expand our search
area to 9.9 is not same as 2 or 5. So now 9 has, now we've reached the
null, we have reached the leaf node so there is not further,there is no way,
there is nothing more to look forward to,
so this returns a null value.
to 11. Then 11 expands and looks on the right side, is 5 same as either 2 or 5.
So 5 is same
as this so this,this guy returns 5 to 11. What this means here,what
this means is that 11 cannot be the lowest common ancestor because it's
getting a null from one side and a not null node from the other side
so 11 is ruled out. So what 11 does is just takes it,takes this not null node
and returns it back to 6.
So then 6,
so now 6 gets a not null node from the left side,a not null node from
the right side which means that 6 must be the lowest common ancestor of 2 and
5.
So then 6 realizes that and it returns itself to the,to the,to it's own parent
which is 3.
So now 3 gets a 6 from the left side and now it's going to do is expand the
search on the right side.
So 3 doesn't know that we have found the lowest common ancestor so it will continue
to search.
So it,we go to 8. 8 is not same as 2 or 5 so we go to 13, 13 is not same
as 2 or 5,we go to 7, 7 is not same as 2 or 5 so 7
returns null and then 13 returns null and then 8 returns null. So at this point
of time
3 realizes that it got a not null node from the left side and it got
a null node from the right side
so then it knows that the lowest common ancestor must be the node returned from
this side which is 6. So 6 is the
returned node. We could have optimized things a little bit by checking that
the returned node from here is 6 and 6 is not same as 2 or 5 which
means that 6 must be the
lowest common ancestor,so we could have terminated our search and not go at all on
the right side of 3.
But for simplification purposes i just explained the entire flow.
Next let's look at another example. Now we're looking to find the lowest common
ancestor of 11 and 8. So again we start from 3. 3 is not same as 11 or 8
so we go on the left side
6 is not same as 11 and 8 so we go on the left side.
2 is not same as 11 and 8,we have reached the leaf node so we return null from
here. Then 6 continues to search on the right side,we, this node is same as this
11 so we stop instantly here and return 11.
So 6 got a null from left side and 11 from the right side
so 6 definitely is not a,not a lowest common ancestor so it's just
going to propagate this 11 up to 3, so 3 gets an 11 from the left side.
Then 3 doesn't know that we have found the lowest common ancestor or not so 3 will
continue looking on the right side.
So then we go to 8 and we check if 8 is same as 8 or 11. So 8 is,this 8
is same as this 8,
so then this returns 8 value.So we stop immediately and return this node.
So then 3 gets a not null from the left side which is 11 and a not null from
the right side which is 8 which means that 3 must be the lowest common
ancestor of 6, 11 and 8.
So 3 returns itself as the lowest common ancestor,so 3 is the lowest common
ancestor in this example. Let's take one last example. Now we're looking for a
lowest common ancestor of 8 and 7, 8 and 7.
So we start from 3, 3 is not same as 8 and 7 so we go on the left side,
6 is not same as 8 and 7
so we go on the left side,2 is not same as 8 and 7,8 or 7 so this
returns null.Then we go on the right side of 6. 11 is not same as 8 and,8 or 7,
9 is not same as 8 or 7 so 9 returns null. Then we go on the,
we go on the right side, 5 is not same as 8 or 7 so this
returns null. So 11 is getting null from both the side so 11 is not
going to be anyone's ancestor.
So 11 returns null from itself. So six gets a null from the left side, 6 gets
a null from the right side
so 6 is not an ancestor either,lowest common ancestor either so it returns null.So now
3 will expand search on the right side so we go here and 8 is same as
this 8
so we instantly stop and return 8. So now 3 gets a null from the left
side and not null from the right side so it propagates that not null value up,
so basically meaning that 8 is the lowest common ancestor of 8 and 7.
So as you can see how it works,even though 8 was the ancestor of 7
using this exact same algorithm we figured out that it,this algorithm
also works in a case where one node is an ancestor of another node.
Next let's look at the code for this algorithm. Code here is extremely simple.
So the main function is 'lca' lowest common ancestor. The node is root which
is the root of this binary tree and node n1 and n2 are the two
nodes whose lowest common ancestor we're looking for and this returns that lowest
common ancestor.
So this is a recursive function. So if root is null then we instantly return
null.
If root is same as n1 or
root is same as
n2 then we return this root.
Otherwise we go into the recursion on the left side of the root passing same
n1,n2 and going into the recursion on the right side of the,
right side of the root passing same n1, n2 and then we get this two nodes left
and right and remember this is happening recursively for every node.
So we get this 2 nodes- left and right for,this happens for every node,if
left is not null
and right is not null what that means is I'm getting a not null node from the left
side, I'm getting a not null node from the right side which means that one of these
two nodes were found on my left side and my right side which means that this
root is the lowest common ancestor so we return root otherwise if both left
and right is null so then we return null because neither of this 2 nodes were found on
the left and right subtree of this root and otherwise if these 2 doesn't
happen then we just return the node which is not null,among this left
and right. So if left is not null return left otherwise return right.
So as you can see this code does exactly as what we discussed before with
the help of example.
So the runtime complexity for this algorithm is O(n).So this is all
I've to talk about lowest common ancestor. Please like this video,share this video
comment on this video,check out my facebook page and check out my github
link.The link to this code is in the description,description section of the
video.Thanks again for watching this video.