Hi, everyone.
So in this video, we are going to solve this question, find the least common ancestor, the short
form is basically LTA, least common ancestor.
So I have to find the least common ancestor of a best tree BSD, basically binary search tree.
OK, so input will basically be three things.
So first is the binary.
And then two nods.
OK, so three things will be input the military and two nodes, and we have to find the least common
ancestor of these two nodes.
OK, let us consider an example to understand the question.
OK, so consider this military.
OK, so this is a binary tree.
What do you have to do?
So let us first find out the least common ancestor of two nodes, then in 14.
OK, so 10 in 14 either do not and we have to find the least common ancestor.
OK, so this is 14.
OK, this is 14.
Now let us find out.
So what are the ancestors often?
So the ancestor of 10 is basically doing it and 20.
OK, so ancestor of 10.
So I'm writing here the ancestors of ten are basically 2L eight and twenty.
Now what are the ancestors of 14?
So the ancestors of 14 are basically twenty eight and 20.
OK, well eight and 20.
So what we have to do so I have to find first the common and least it should be standard, should be
common.
So 2L is the least and it is the common OK.
So 2L is basically the lowest common, least common ancestor of 10 and 14.
OK, so I hope you understand.
OK, so 2L is the least common ancestor of 10 and 14.
Now let us consider it N14.
OK, so basically.
Let us find out the least common ancestor of it, and 14 so far, it basically the node itself is also
ancestor.
So this is it.
And twenty by the definition.
OK, and 414.
So 414.
This is basically 12.
And then we have eight and then we have 20.
OK, so eight is the common.
So basically, the output for this is basically eight.
OK, now consider this example.
So this is a.
This is also about, OK.
Both are bisdee.
Now, let us find out the least common ancestor of 28, Cerveris, too, so this is true and this is
it.
So least common ancestor is now let's find out the last common ancestor of two and four.
So this is two and this is four.
So the least common ancestor is to itself.
OK, now let us find out the least common ancestor of.
Let's say seven and nine, so for seven and nine, it will be eight.
OK, so this is seven and this is nine.
So last common ancestor, is it?
OK, now let's find out the least common ancestor of basically zero and seven.
OK, so basically this is zero and this is seven.
So the lowest common ancestor is basically six.
OK, so at least a common ancestor is six.
But really, the least common ancestor of.
Let's say three and zero.
OK, so four, three and zero, the last common ancestor is basically two.
OK, so the least common ancestor is two.
Now, what will be the least common ancestor of basically zero and nine, so this is zero.
This is nine.
So lowest common ancestor is six.
OK, so now I hope you understood what is the meaning of least common ancestor.
OK, so the input will be two things first observed by necessity and then the two nodes and we have
to find the earliest common ancestor.
OK.
Now, let's see how we can solve this question.
OK, so let us consider this example.
So let's say twenty eight, 22.
So I have to consider a OK, because in the question is given.
So this is a.
OK, so this is a beast.
And let's say I have to find basically the least common ancestor of tuners and let the two nodes, 13
and 14.
So the logic is very, very simple.
What we will do, we will try to find out these nodes.
So the main idea, the main idea behind the main idea to solve this question is basically find node.
So this is the idea.
OK, so we have to find Bernard, so let us start finding the A..
OK, so how we can find a..
Basically, I will start from the root node.
So this is the root node.
Now, the input is basically about so compared to 20 with Ben and 14.
OK, so 20 is basically good, then 10 and 20 is basically good, then 14.
So obviously to find out the ten, I have to go in the left hand side and obviously to find out the
14, I have to go in the left hand side because the given is basically bisdee.
And for Steve, this is the root node.
So that's more level usually present in the left hand side.
OK, so that's why if I want to find out then because the idea is find the nodes.
So if you want to find then go in the left hand side.
If you want to find the 14, then also go in the left hand side.
So now let's go to the left hand side.
So at the left hand side I have it.
So now let's compare again.
So it is basically less than 10.
And it is basically less than 14.
OK, so now in this case, what will happen in order to find out, then I will go in the right hand
side in order to find out 14.
I will go in the right hand side because this is a BSD and investee.
If this is the root node, then the larger value will lie in the right hand side.
OK, so now let's go to the right hand side.
So right hand side is basically equal.
OK, so now we will compare tool.
So basically Google is basically good dentin and well is basically less than 14.
OK, so in this case, what is the scenario?
In order to find out, then you have to go in the left hand side.
OK, in order to find 14, you have to go in the right hand side, OK, so here we have a contradiction.
OK, so this condition is this condition is go in the left hand side and this condition is telling me
to go in the right hand side.
So where should I go?
So the answer is basically do not go anywhere.
My answer will be to.
OK, my answer will be equal, so that logic is very simple whenever you have a contradiction.
So should I go in the left hand side or should I go in the right hand side?
So you have a contradiction with every contradiction.
So obviously that the truth is your answer.
So you can see the L.C of 10 and 14 Daltry often in 14 is basically equal and is my answer.
Very, very simple.
OK, you got the logic, so let us consider one more example.
OK, now suppose you want to find out the LCA of, let's say, 1814.
So basically all of 1814, is it only.
OK, now let us follow this logic.
So the idea is basically find out Donald's idea is very simple.
OK, so I will start with 20.
I will start finding from the root node, so to David it so 26 it guarantees then 14.
So this condition stays go left in order to find out that this condition says go left in order to find
out 14.
So I will go left.
So if I will go left, I have it.
OK, so compare it.
So it guerdon it and then the second condition is eight.
Guerdon 14.
OK, so basically in this situation, so this condition is telling me to go right.
And this condition is basically false.
OK, so this condition is basically false.
So what you can do in this case also, I would honestly, I will stop, OK, so in this condition also
I will stop.
Because this condition is false, it is not guarded, so where should I go?
OK, so what I will do basically it is it goes to it.
So whenever you will find out the node, whenever you will reach one of the nodes, you will stop and
the answer will be it only.
OK, so there are two conditions to stop.
First, when there is a contradiction and the second condition to stop is basically when you find out
any one of that would OK when you reach any one of the two nodes.
So in this case, I reached it.
I reached Noraid.
So I will stop.
OK, so very, very simple.
We just have to find out the nodes.
OK, now, basically in discussion, discussion, we have an assumption, OK, what is the assumption?
So assumption is basically that given to NATO military that donors are present in.
So this is the assumption.
Now, let us take one more example to understand it in a better way.
OK.
So let us take this example.
OK, let us take this example and we have to find out the energy of 200 l.c after one year to start
with six.
So six is good, then to six is basically less than eight.
So in order to find out, do I have to go in the left hand side in order to find out?
Did I have to go in the right hand side?
So whenever there's a contraction, we will stop and our answer will be six.
OK, so six is my answer.
You can see six is my answer.
OK, now let us try to find out the LTA of basically let's take zero and three, OK, zero entry.
So I have to find the LC of zero entry.
So my answer should be to OK, my answer should be to Lalaji.
So I will start with six.
So six is basically good then.
Zero.
Six is basically good then three.
So go left.
Discretional also says go left.
So if I will go left I have to now two is basically greater than zero.
So in order to find out zero go left, two is basically less than three.
So in order to find out three go right.
OK, so there is a contradiction.
So my answer is basically to OK, so two is the right answer.
So I hope you understood the logic.
Now, one more thing.
I told you so basically.
What they have to do is basically be in the tunnels and they exist in the body.
OK.
So this is the assumption of the question.
So this is basically the assumption of the question that both then would be in Cuba does not exist in
that tree.
OK, so if this assumption is not there, then what we have to do.
So first of all, we have to find whether the boat the not exist in a tree or not.
OK, so if the assumption is not there, if the assumption is not there, my first step is basically
what we have to do.
So in the first step, I will check whether the nodes are present in that tree or not.
OK, so if the nodes are not present in the tree, so if any of the node, if any of the two nodes.
So if any of the two nodes are not present in that tree, then this question is basically invalid question.
OK, this question is invalid question because we have to find the least common ancestor of two nodes,
B and Q, other two node.
So both and also the existing debris.
Otherwise this question is basically invalid question because LC will not exist.
OK, the common ancestor will not exist if any of the two nodes are not present in the tree.
OK, so first step is basically very simple.
We have to check whether two NATO is in a tree or not.
OK, but the question it is that do not will always be present in the tree.
So we do not have to check this condition.
We can directly write our code.
OK, so now let's write the code.
So writing code, very, very simple.
So what I have to do, so I have to write to the condition.
So what I will do, I will compare but that I have to go left or right.
So if raw data is basically good then so be encoder to node.
OK, I have to find that LC of two nodes which are Banku, so if it is a good then B and basically the
root data is also good, then that means in order to find out Banku I have to go left.
OK, so for going left I can write.
Rudik was left off route.
Simple.
Now the second condition will be so if the root data is basically less then B and similarly, if the
root data is basically less then Q Then in order to find out, in order to find out B and do what I
have to do.
So I have to go.
Right.
So in order to go right, what I will write.
So I will write a root cause right of root.
And in the third condition basically there will be conflict.
OK, so here root data is good then B and good.
Then you hear the raw data is less than B and left in the third case, the conflict.
And if there is a conflict, so in the third condition, the L Spartacists or if in the end if part
and this is the end.
So in the conflict in the elzbieta there will be conflict.
So whenever there's a conflict we can stop and we can return to OK, we can return root.
Simple.
So this is basically a data solution.
OK, this is basically iterative solution.
There's no need for decoration here.
OK, so now let's write the code.
So basically, what is certain types of return type is old style.
OK, so in this case for 2008, when I I'm returning, I am returning six.
So six is basically I do not start OK, so I have to return North Star and be you also also.
OK, so what I have to do.
So I have to search for Nords.
OK, so.
Wildwood is not a ghost tunnel, so Wildwood is not in first condition, so if Rudy down, so I'm using
this condition, OK, this first condition.
So basically, if the root value is greater than the value.
So if you'd value is lower than the value of P and the root value is basically greater than the value
of Q.
So in this case.
And I to find out, you have to go left.
So let us go left simple now in the elusive condition.
So basically, if the.
Route value is less than P-value.
And root value is less than.
Q Value.
Then in order to find out Banku, you have to go, right?
OK, so basically Rootes route, is it closed?
All right.
Off route.
Simple now in the Elzbieta is conflict, whether I should go left or whether I should go right.
So in the last part you will stop and you will return the answer, which is it would only OK.
Now, in order for the completion purposes.
OK, so I have to return it in order.
So for the completion purpose, I have to return something here.
OK, so let's get it done here.
So again, this line will never get executed.
OK, this line will never get executed.
This is only for the completion purposes.
OK, so this line is important only for completion purposes.
This line will never get executed.
OK, so this is the computer code, very simple code.
OK, so compare the root value.
So this is basically this one.
OK, so compare the root value with the value of P and similarly compare the root value with a value.
OK, so both Benguela in the left to go left in this case, both be in line, the right to go right
in the part this conflict so you can return.
Now first we will run our court and then we will try to submit our call.
OK.
Now, there are some.
OK, let's meet again.
OK, guess clavichord is working fine.
Neither does discuss their time and the space complexity.
OK, so basically these are the two conditions.
And this is the conflict, OK, whether I should go left or whether I should go right.
Now, what is the space complexity?
So this is the iterative version.
OK, so we are using it to we are traversing the tree in the outer division.
OK, so the space complexity is big off when we are not using any stick.
Now, what would be the time, complexity, time, complexity is big often, so this is wrong.
This is not because we are not going through each and every node so -- complex it is.
Basically we go off edge.
So what is Hetch Hetchy is basically the height of the tree.
That is basically the height of the tree.
OK, so this is wrong.
I'm going back to this big often only when you are going through each and every node, but in this case,
you can see carefully at each line.
I am taking the condition.
I am taking a data situation whether you should go left or whether you should go right.
OK, so if this is the three letter.
So this is the Fruitland.
So at each node, I am taking the condition whether I should go left, I am digging, I am taking a
decision whether I should go left or whether I should go right.
OK, so suppose first I go left, then I go right, then again I go left.
Then let's say I go right.
And then finally here I will stop.
OK, so basically what I am doing in the worst case, I will reach here, I will reach the lymph node.
This will be the worst case, ok.
So basically the height of the trees, let's call it the height of the trees five, so this note is
present at depth five.
So I will reach in the worst case, I will reach this height.
OK, so what is happening here is at each node.
At eight a.m., taking the decision whether I should go left or whether I should go right, you can
see yourself.
I am taking a decision whether I should go left or whether I should go right.
OK, so I am not going through each and every node.
So that's why this is the wrong time complexity and this is the correct time complexity.
OK, big off Hetch Hetchy is basically the height of the.
OK, because at every note, I have to take a decision whether I should go left or whether I should
go right.
OK, so finally, time complexities, big off edge.
Where is the height and the space complexities?
Big off one.
OK.
So if you have any doubt in this question, you can ask me, OK, thank you.