Hi, everyone, welcome back.
So in this video, we are going to write the code for this problem, but before writing the code, let's
first it is our screen and let us summarize all these four conditions, all these four cases, and then
we can start writing the code.
Fine.
So what we are going to do here is so first let me write here that the first cases, if the left is
null, write this one if left and right.
So if left is null, write is also null.
Then we discussed that Banku not found, so if not found the lowest common Chesterville, obviously
none.
So my answer will be then I will return an.
The second case is basically left seasonal right to second guess is your left is.
So in that case, whatever value you are getting from the right Sabry, you are returning that value,
right.
So left and right is not null.
So in this case, your answer will be right.
This is the answer.
Tardigrades can be left is normal when you are the left hand side and right is null in not present in
the right subtree.
So in that case, my lowest common ancestor will be whatever value I am getting from the left subtree.
That will be the lowest common ancestor.
So I will be left for TKIs can be left and right both exist.
So left is not null, right is also not null.
Both values at present.
That means one of the node is laying in the left subtree and another node is laying in the right sempre.
So that is the definition of lowest common ancestor.
So in that case, my answer will be ruled itself fine.
So now let's remove all this and now we can start writing the code.
So being other two nodes and we need to find out the lowest common ancestor for these two nodes and
we have discussed all the recursive cases.
So now let's start writing the code to first of all basis.
So what will we base case?
Base case will be if your tree does not exist, right.
So if tree does not exist, then what will be your lowest common ancestor?
Obviously null lowest common ancestor will not exist.
Right.
And now we discussed that if root is itself.
Is it going to be or root is equal to.
Q So in that case, what will be the lowest common ancestor.
What.
My answer.
My answer will be root itself.
Right.
We have discussed this otherwise, but we need to do we need to search in left and right.
So this is left.
What I will do, I will call the function lowest common ancestor.
And I will give them their subtree.
B and Q search B and given level, and similarly, I will do the opposite for this, I will also call
on the right Sabry because this is not bisdee, so it cannot decide in which direction you can go.
So you need to go in both the direction and try to search for P and Q wait.
So I'm searching for Bianca in the subtree as well as in the right subtree, fine, and now we discussed
four cases.
So first case is very simple.
So if left personal and so this is left not.
And this is left.
So if left is null and
void is also null.
So we discussed that my answer will be none.
So what I'm going to return, I will return.
The second case was, so this is Altaf.
And if left is null, left is null and void is not an all right exist.
So in that case, we discussed that my answer will be right, so I will return right Tariq cases.
Left is not null and riot is null.
So in that case, we discussed that our answer will be left and it finally fought case enfold case.
My answer is rude.
So let's directly return route.
And that said, very simple court.
Right.
Let's test our code.
Yep, now a little.
So, yeah, our goal is right, our goal past all the test cases and you can see this is very simple.
All right.
And what we can do, we can write in our code on one of the examples given indication.
So which example we should pick?
Let's pick this one.
Right.
And let's try to understand how the code will work.
So the value of B is five and the value of Q is four.
OK, so I will stand here.
I will compare the three is not close to five and four, so I will go in the left right now with five.
So five equals five, right.
Five equals five.
We will hit this.
In that case I'm going to return.
So I will return five.
Right now from left, I got the answer, now I will call on, right.
So check for so when is not close to five and four.
Zero is not close to five and four zero will call on left.
It will get nine zero will call on right.
It will get nine.
And whenever we are getting help from both sides I will return.
So zero will return and then one will call on.
Right.
It will call on left.
It will get another caller right.
It will get well it is getting mail from the side.
That is case one.
So it will also return.
All right.
So I am returning and returning also for one.
I'm getting mail from both sides, so I will also return.
And now we have this case from the left hand side.
I am getting five from the right hand side, I am getting well.
So this one.
Right.
So in this case, I am returning left, so I will return five and five is the right answer so you can
see how cold is working.
Let's try another call for one more test cases, one more basically three which is given in the indication.
And let's try to understand how our code will work in that case.
Yeah, so let's start the value of B and give this, and this is the root node, so compare three with
five and one, they are different.
I will call on left.
So five and five they are same.
That means the base case.
So my answer will be five and it will return five.
So I will call on this now.
I will check.
So this is one, right?
This is close to this one.
So I will directly return one.
Right, you will like it and do so for three, for three left is not all right, is not an let Miss
Gaisford left exist, right exist.
So in that case, the answer was rude itself.
So my answer is rude itself, which is three and three is direct answer.
So our goal is working.
And now let's discuss their time, complexity.
So what will happen?
You need to go to each and every node.
You will go to each and every time complex it will be, and the total number of nodes that end certain
complexities big off and.
Very simple, right?
And similarly to two lesbians complexity, so if you have Destry.
So if you have this tree, school tree, so what will happen, all the nodes will be present in this
sort of space complex.
It will be big often.
So this is the time and the space complexity for this problem.
Right.
So the code was very, very simple.
But we are doing simple biscuits and other simple, very basic case.
Then you need to search on left and the search and.
Right.
So I'm calling on left and right and then these four cases late, then these four cases and that very
simple recursive algorithm, very simple recursive called.
So this is all over this video, guys.
I will see you in the next one.
Thank you.