Hi, everyone.
So in this video, we are going to write the code for this function, Belpre, so you can see the input
is preorder traversal and traversal, but if you will see our function, so we are doing something like
this, we will create a function and we will give you another traversal period.
And we also give these four values simple.
So first, let's create a helper function.
So I want to create a helper function.
It will return.
So let's say the name of the tree is built tree helper.
It will return the root of the tree, so Belpre helper function and what it will take.
So it will take a period reversal in order to start in order and start preordering for constructing
the tree.
So I need a vector of indigenous.
So this is an ordered.
I need another vector for preorder.
So that area three already.
And if you will see in order starting or that end, preorder, start preordering.
So I need India in order to start.
Integer in order and I need preorder.
So this is pretty early start.
And Fiordland.
Preorder and.
And we will write this function, so it is taking a lot of variables.
So if you want, you can short their names also.
So the names are very big, so let's name it.
In start, so this is in order to start.
This is in order to end, and this is preorders start.
This is preorder and.
So let's.
So instead of start, we can also write as in order to start, this is in order and.
This is Preordering Start, and finally, this is.
So this is preorder, and so now it's looking good, so I am digging in already.
I am taking preorder as input and start in order and really start own.
So we know we know dysfunction.
So what is our approach?
Our approach is very simple.
We will construct the root node, so I am writing it here.
So our approach is very simple.
I will construct the root node and then I will call the function.
I recall the occasion for building the left subtree.
I will call occasion for building the right subtree and I will construct a node and general construct
these two separate simple.
So for root node, what do we need?
So just remember the order.
What is preorder.
The order is first, you print the root node, then you print the live separate, so first you print
the root node, then you print the left subtree and then you print the right subtree.
And what is in order?
And all that is left to right, so first you print the left subtree, then you print the root node and
then you print that out simply.
So let's construct the route, not first.
So I want to construct the note, and it is basically this index, the first index.
So since this function is going to be recursive function, so first of all, we need to be able to write
the code for the base case and what is the base case ampitheater.
So for an area in order to start will be greater than in order end.
Or you can also write like this, you are preorder.
Start will be greater than preorder and so you can use any of them.
So, for example, I'm using an order starting ordering.
So this is the best case.
This case means your area is empty.
So for Empty-headed, which would be a tree, so your tree will be null, right for them.
Pertierra The output will be empty.
So I am returning them.
So now let's discuss about the raw data.
So what is the raw data?
So raw data.
It's basically the first element, so this is the reversal traversal, so the first element.
So let's copy this.
So the first element of deputed traversal is going to be my route.
So zero.
No, this is wrong.
You cannot write zero because you are using recursion.
So this is your start.
So basically, this index is not zero.
You will not zero.
You will write preorder start.
So this index is preorder start.
You are passing preorders start.
Remember, you are passing your Nasrat.
So writing zero will be wrong, so zero writing zero will be wrong.
So this is a start.
So this is your start.
So let's cooperate here, but start.
So now we know what is the raw data.
So what we need to do, we need to find out this year the values.
We need to find out.
We need to find out the earth values.
What are the values left in order to start left in order and right, left, right, left and right,
preorder, start, right, preorder and left in order to start, left in order and right in order to
start right in order.
And so we need to find out eight values so that I can construct the left and the right subtree.
So let's see how we can do that.
So I need left in order to start.
I need left in order and.
I need to find out left.
Preorder.
So left before the start.
Left the end.
And similarly, these four values for the rights are also for calling on the right pray.
So I need.
Right.
In order to start.
I need a ride in order and.
Similarly.
I need right.
Order start.
I need.
Right.
Pre order, and so we need to find out all these great values, so after calculating all these great
values, what we need to do, we have the raw data.
So as discussed, what is our plan?
Our plan is first to construct the root node and then call that equation for the left separate and call
that equation for the right supply.
So let us construct the root node.
So we have the raw data, we have this raw data, we can construct the node, so three.
North Star route is New Reinold and will pass that data.
So now our first step is done, we have constructed the route note and now let's call that a question
for the left and right separate.
So we need to call the recursion.
So what is I want to construct the left of route, so we will call this function for constructing the
so called function.
It takes in order to sell.
So let's give order traversal.
It takes traversal.
So let's give traversal.
Now it needs in order to start, so I'm calling on left, so I will give left in order to start.
So then it needs in order, and so I have left in order and.
Then it needs to start and build and so I am calling on left, so left to preorder start.
And this is left preorder and.
Simple, right?
So now you're left has been constructed and now what we will do so after the left subtree has been constructed.
Now let us also construct our rights free.
So now I want to construct my rights apprec, which is, again, I will call this function military
helper, it will construct my right subtree.
So I need in order traversal.
I also need burette traversal.
So it is asking for in order to start, since I'm calling on rightly so, I will give right in order
to start.
Then it needs in order, and so I will give right in order to end.
Then it needs to start and be all around since I'm calling on the right subtree, so I will give right
before the start.
And I will give right preorder and.
Simple, so now our rights are free, so our complete tree has been constructed, we constructed the
root ourselves here, then the equation we call occasion for the tree has been constructed.
We call the occasion for the right pray.
You can see we are calling the occasion for left subtree and for iSuppli and we are teaching them.
So this connection has been established, this connection has been established and now we will return
the rule.
Since our tree is ready, we will return the road.
So after constructing the entire tree, I will return the road and how I will call this function.
So I will call the function tree helper.
So first, let's find out what is the total number of elements so you can do in order their size.
So you can do in order size or you can look the number of elements is going to be seen, right?
So after finding out the size, I will call this function helper.
So I want to return the root node, so return Belpre helper it takes in order.
So I will give this in to.
Then it takes preordering.
So this is my priority.
Then it takes in order to start in order, and so in order to start zero, I have to give them in order
to start from zero and the end indexes and minus one Briona, start from zero order and at index and
minus one.
So now everything is complete, so we have the majority of the time, so what we need to do.
So our goal is our goal will work, we just need to find out these eight values, if we will find out
these eight values correctly, then our entire code will work.
So we will find out these eight values in our last session.
So let's find out them again.
So the main problem, so this is basically a mathematical problem.
This is not a difficult problem.
The difficult part is finding out these eight values correctly.
So first, let's start filling those values, which are very obvious.
Let's start feeling the values which are obvious so left in order to start.
So see, this is what is left in order to start.
This is the same as preorder start.
So let's fill this value because it is very obvious.
So this is same as, OK, so I did one mistake.
This is not preorder.
This is in order to start.
In order to start your day start.
This is Reporter End and this is in order.
And so first, let us fill all these values.
So in order to start left, in order to start.
So left in our last are the same as in order to start.
So this is in order to start.
OK, so left in order and now left in order, it is difficult right now, left to start.
So preorders start left is very simple, you just need.
So this is also very simple.
This is so what is left preorder start.
So this is preorder and this is the starting point.
So that means the preorders start plus one simple.
So this is preorders start.
Plus one.
A start plus one, what is left preorder and so preorder left and right now, that's difficult to calculate.
So let's discuss about right in order to start.
So in order area and right.
So right now it is also difficult, right.
In order and so right in order.
Right.
And so the system is right in order and is the same as in order.
And so this is the right in order and at the same as in order.
And so let's fill this value.
So in order and.
Right, preorder, start, so preorder and right to start, we don't know, right preorder and so right
before the end is same as preorder preordering.
So this one is also very easy.
So this is same as preorder and.
So now what is the situation so we have calculated for values very easily, so disvalue then Disvalue
done this done and is done.
We have calculated for values and we need to calculate for more.
So let's see how we will do that.
So let's discuss about this value left in order and.
This is the left in order and we need to find out the index of this element.
So, you know the root element.
We know the root element.
So we have the raw data.
What we will do, we will search for root in the traversal.
We will use a for loop.
We will search for the root.
You will find out the root by finding out the root.
I mean, you will be able to find out the index.
So let's call it a root index.
And what does this value?
This values root index minus one simple.
So this value is the same as root index, minus one.
But first you need to find out what is root and so forth, finding out the truth.
Next, you need to ETrade already in order at a solid let's rate.
So let's try to find out the root index.
Let's see, the value of rootlets is minus one and let's find out the next four and.
I equals in order to start.
So this is the start when I did over the Internet, so in order to start.
I didn't know what it was to in order, and I placeless.
So if the order, Eddie, so if the order, Eddie.
Ofay is same as the raw data, then we find out our next so rude index is basically a and then we will
break.
So now when we will come out of this whole loop, so when we will come out of this for loop, we know
the routine, so we know the index of this element.
So left, so left in order and is just rude index minus one.
So we know the value this values root index minus one.
So is it possible that after coming out of this value the value of the Nexus minus one, so it is only
possible in case the input is wrong.
So here the value of the index is minus one.
If the values minus one, that means your input is wrong, your input is wrong.
And one more thing.
Our code will only work if there are no duplicates.
So we are assuming there are no duplicates in the adding.
For example, if this new test for this, it is also food and we have food multiple times, for example,
food is also here for is also here.
Albacore will not look.
So we are assuming no duplicates and input is also right.
So our Rouda next will not be minus one.
So we do not have to overreact all these things.
So now we know what is left in order, and so this is routine X minus one.
So the next.
Minus one.
OK, what is left pre order and.
So this value is a little difficult to calculate, so we need to find out this value and I told you
so, the number of elements in the left will be the same.
So these elements so these number of elements and these number of elements will be.
So we can use a condition like left in order and minus left in order to start.
So these are the number of elements is same as left preorder and minus left start.
So we need to find out this value.
We need to find out this value.
And we already have three values.
So let's find out this value.
So this values the same as we can do.
So we move this to the left hand side.
So this is left.
Preorders start.
Left before the start.
So left preorders start.
Plus, left in order and so left in order to end.
Minus left in order to start left in order to start.
Simple, right?
So now we have also calculated this value.
So now let's discuss about how we can calculate, right, in order to start so right in order to start.
So in order to do so, in order to sell and this is the starting.
So what is starting RWD index plus one?
So this is also simple.
So this is basically.
The next plus one.
We already calculated right in order and and this is the last remaining value, right, the start,
so we need to find out pre order and right before the start.
So.
Right.
And preorders start.
So we're desperate to start.
We can redeem this value.
So Disvalue plus one and this is left pre order end.
OK, so this is this is left before the end and plus one.
So this value plus one.
So copy this value left, preorder end.
So this value plus one, so now I think we have calculated all our values correctly.
So now I think we have calculated all our values correctly and our culture work fine now, so let's
try to test our gold and learn more everything.
So let's first we will run our code and then we will submit.
OK, so now you're something called.
So basically, our solution got accepted, so our solution is a hundred percent correct.
So basically, what is the most difficult part of this problem?
So the most difficult part of solving this problem is to just find out these values correctly.
So if you will find out these eight values correctly, then this problem is very easy.
So this is basically a math problem.
A simple, OK, just logical, there's nothing much complicated here, just find out all these values
step by step and you will be able to find out everything.
So this is it from this video.
I will see you in the next one.