Hi, everyone, welcome back.
So in this video, we are going to discuss about a new problem, which is find the lowest common ancestor
of a binary tree.
So we have already solved this problem for binary search tree, but now we have binary tree to the branches
with the same, except that now we have a binary tree and not the best.
So in binary, how we can solve this problem.
So that will be very, very simple.
Using recursion, we can easily solve this problem.
So for example, this is my route node, right?
This is my route node.
So first of all, I will check.
So if P or Q is equal to the root node, then my answer will be node rate.
So very simple.
If your root node is equal to be or your root, nor does it close to Q, then the answer is root and
the answer is root.
So we will return root, right?
So my answer will be root and I will return root.
So now if this is not the case, if Q is not close to root, so what I will do, try to find B income
in the left subtree and try to find being in the right.
Sabry So in case of BSD we can compare root data with the data point and we can decide whether we want
to go left or whether we want to go right.
But since this is a binary so we cannot decide whether we should move left or we should move right,
so we will go in the other direction.
So I will call that equation and I will search B and similarly I will call that goes in the right subtree
and I will try to search B and you know, there are four possibilities.
So let's talk about possibilities.
One, right.
So first, possibility is
being not present in the left subtree.
So it will return B and also not present in the right subtree.
So I will return null.
So being not present, not present in the right subtree.
And also the root data is not close to the data of Bercu.
So B and Q is not present in the.
So my answer will be null.
This is the first case.
Second case can be so in the left subtree being not present I, I'm returning null in the rights of
prepend.
Q is present so I will get some data, I will get basically the root node.
So Birute not Emin's the lowest common ancestor rate.
So FBN good presented the right subtree.
Let's say it is returning the node X X is the lowest common ancestor.
So what I will return, I will return X because X is the answer.
Rate X is a node X is an order.
So I will return the node X and X is the lowest common ancestor.
Fine particles can be the of this one being who is not present in.
Right.
So I will get an L from right and B and you are presently left.
So I will get the answer because it will give me the lowest common ancestor.
So I will get the answer that the lowest common ancestor is Node X, so I will return node X therefore
TKIs fruitcakes can be this is my route.
So one of them is present in the left subtree.
So I will get x rayed that it is the left subtree and similarly I will get some value from the right
supply.
So what I am saying is we can be present in one subtree and gilgan representing another subtree.
Right.
So let's remove actually X and Y.
So here what I want to say for a node, fruit node, what is happening B is present in another subtree
and Q is present in and it is A pre rate or vice versa.
So here we present and Urbis present.
So I will get some value from here.
I will get some value from here.
So in this case, what will be my answer?
What will be the lowest common ancestor?
I think the answer will be root itself.
It so far ruled a. one of the north is lying in the left subtree and another note is lying in another
subtree, so that means the lowest common ancestor is basically the root node.
So I have a little root, right.
So these four are the basic cases that we need to handle.
And if we are able to handle these four cases, then we are done, then we can easily solved discussion.
Right.
So again, first of all, what I will do, I will check this whether the route itself is going to be
OK, if that is the condition, my answer will be ruled itself.
Otherwise, I have these four cases for second, third and fourth cases and I will write the code for
these four cases and that that will be the complete called the coding part of this problem is really,
really simple.
So you can do the coding part yourself.
And in the next redo, if you are not able to do the coding part yourself, then you can always watch
the solution, the next video.
So we will be writing the code together in the next video.
So this is all the supervised.
I will see you in the next one.
Thank you.