Hi, everyone.
So in this video, we are going to solve this question, so we need to construct the tree and we are
given the poster traversal and we are given the.
So it is very similar to the last problem that we have solved.
So instead of preorder, we are given post order now.
So, for example, if this is the only or traversal and obviously the number of elements will be the
same in the traversal, so how we can construct that tree.
So first of all, you need to remember what is Deposal Trevathan?
So first we will bring the left sempre, then we bring the right subtree and then we will print the
data and what is in order to listen.
So first we print the left subtree, then we will print the data and then we will print the right.
So this is in order traversal.
So for example, first of all, I need to construct the root node.
So for the node in the portal traversal, the last element is the root node.
So the last element is the root note and now it will do so.
It will search three in two separate left and right separately.
So so each tree he was those three the traversal this is three.
So this is the left subtree and this is the right separate.
So basically nine will be present in the left sempre and 15, 20 and seven is going to be present in
the right subtree.
And now what we will call qualification for the left subtree.
We will qualification for the right subtree since there is only one node.
So this will be only three and nine.
And now let's discuss about 15, 20 and seven, so 15, 20 and seven, so again, so given the big problem,
what is the big problem?
You have to construct that, given the traversal of the entire trillion, given the reversal of the
entire.
So now you want to construct only the right hand side.
You only you only want to construct the right subtree.
So you need the right in order traversal and you need the right traversal.
So the elements are 15, 20 and seven.
So this is the 15, 20 and seven for the right subtree and 15, 27 for the right subtree.
OK, so first of all, we need to construct the root node and root for this present.
At last root is present that lasts for 20 years or so.
20 is the root node.
Now, also not in the traversal, so search, so here is 20 or so, 15 is the left subtree and seven
is the right subtree.
So rude before rude.
We print the subtree, after we print the right.
So that means 15 is going to be present in the left subtree and seven is going to be present in the
right spot.
And since this is only one single node, so twenty, fifteen and seven.
So now the right summary has been constructed that's appended here.
So I have 20, then I have 50 and then I have seven.
So you can match our three Salvatores.
Correct.
So now what we need to do, what is our approach.
So our approach is very simple, what we will do.
So let's write first in order and the posterior traversal.
So in order is.
So this is.
The left first shipment, they left subtree, then reopened the raw data and then we print that out
separately.
And what is the traversal?
First, we print the left subtree.
Then we print the right subtree.
And then we print that so routinely printed at last.
So now our approach is very simple, just exactly like the previous one, so this is your start.
This is the in order and index.
This is post order starting next.
This is post order and index, just like the previous problem.
First of all, we will construct the root node ourself.
Then we will build the left subtree and we will build the right separate using recursion support, constructing
this root node.
We already have the root node, so not only the last element of the potion or traversal.
Now let's see how we can call the equation on the left subtree.
So for building the left subtree, we need left in order traversal and left posterior traversal.
So we need a left in order traversal and we need left posterior traversal for building the left subtree
or left in order.
I need left in order starting next.
I need left in order and indexed similarly for the left posterior traversal.
I need left also starting next.
I need left.
First order and next.
And similarly, if we want to build the right subtree, so for building the right Sabry, we need the
right in order traversal and we need the right most of the traversal for right in order to listen,
I need the right in order starting next.
I need right in order.
And similarly, I need right post order starting next, I need right fast order.
And so again, we need to find out the values for values for left.
For values, for building the left subtree and for values, for building the right subtree, so in total,
we need to find out it values.
So let's see how we can find them.
So let's start with left in order to start.
So this is the left.
And left in order to start this seems in order to start this value was very simple, the same as in
order restaurant.
Left in order.
So right now we don't know.
Left post order start.
So left that start is same as postal start.
So this is same as.
Most order start so left and so right now we don't know this next.
So now let's discuss about right.
In order to start, you need to find out right in order to start.
So right there starts right now.
We don't know this value right in order.
And so right now, we don't know this value.
Right post order start.
So.
Right.
Bulstrode start currently we don't know this value.
Right, Bulstrode?
And we know this value.
Right.
What does this value?
So.
Bulstrode and minus one.
So this value is simple.
This is first order and minus one, the one element before the root element.
So now let's discuss how we can find out this value.
So you know where it is root.
You know, the raw data, so you will search for the raw data in the traversal, you will find out the
raw data and we will call it, we will find out the index and we will call it root index, you know,
root index, what is left in order and so left in order.
And this index just before root index.
So this is root index minus one.
This is rude and X minus one, simple and similarly, what is this index?
So this index is basically right in order to start.
So this is route index plus one.
So we know this is.
Route index plus one, what is right in order and so right in order and is the same as in order.
And so this is same as in order to end.
And now we need to find out only two values.
So we need to find out this value and we need to find out this value, how we can find out this value
exactly like we used to find out in our previous question.
So the number of elements in the left will be seen.
Right number of elements in the poster traversable besame.
So that means.
Left in order and minus left in order to start.
So these are the total number of elements in the traversal will be same as left post or that end minus.
Left for or start.
So these are the total number of elements in the post retriever's and they will be the same number of
elements will be same, you know, disvalue.
You know, this value, you know this value.
You just need to find out this value.
So take it to the left hand side.
So this value will be your left shoulder start, plus left in order and minus left in order to start.
And what is this value?
Right post order start.
So you have calculated this value right now.
OK, you are you have calculated this value.
So this value will be just plus one.
So this will be left for Stalder and plus one left Austro the end plus one.
Now we can construct our tree and how we will call our function.
So we will create a function helper function.
We will pass the traversal, we will pass the total reversal.
We will pass in order to start.
We will pass in order and we will pass also the start and we will pass order end.
Simple.
So this question is also present on later.
So this is the question.
We have to construct the binary given the in order and the posterior traversal.
So this is exactly similar to the last problem that we have solved.
You can take the help from our last code and you can just modify that code.
So this is it from this?
We do.
In the next we do, we will write the code.
But what I want firstly, you guys should try to implement the code.
It is just the modification of the previous code.
OK, and I have told you how to find out all these eight values.
How to find out all the data values so you can just modify the previous code.
So this is it from this video in the next video we will start implementing.
So I will see you in the next one.
Bye.