Hello all and welcome back.
So in this video I want to discuss a question which you all have to do.
And the question is construct a binary tree given the inorder and the postorder.
So let's get started.
Now in the last video we actually did a similar kind of a question, but in that question we were given
the preorder instead of Postorder.
So the whole approach of solving this question is again going to be a lot.
Same given a tree.
We know that how we have to imagine it.
And that is going to be our strategy in most trees.
Question.
The reason is the overall structure in which trees are made.
It can very well be imagined that each and every node is a property in itself.
Okay, so great.
Now let us see one example quickly.
We can take the previous example only.
Let me just get this on the nodes.
Maybe we can just have the postorder and the In order.
I'm pretty sure that all of you must have also tried doing the last question at your end once.
That is, after seeing the solution as well.
You have just tried the solution once at your end.
Okay?
If not, then I highly suggest you to do that.
It will be a lot helpful.
Okay, great.
So we saw that the tree which you are getting in this particular case was something like this.
Five and three had a right child.
Now again what we have to follow is something like this.
So we have been given the inorder and we have the postorder.
We just have to see that.
How can we send a cross to each left and the right subtree, its corresponding postorder and the inorder.
So let me write the inorder first.
It's going to be
425136.
And talking about the overall post order, that is
452631.
Great.
Now we know that in order actually means that first we are given about the left subtree.
Then it is the root.
And then we print out the right subtree.
In a very similar manner.
What we are given in the post order is something like the left subtree.
The right subtree.
And the root.
Now in the last couple of videos, when I was doing the question, I explained you the overall thought
process, that how exactly do we reach to this kind of questions?
Right.
We have to understand that what all we know and from that knowledge and taking an example, we have
to make sure that we are able to form some hypothesis or move towards our solution.
This approach is actually which is going to help you in solving lots of questions on any LeetCode or
in an interview.
Okay.
So always trust and properly study all the things you know and remember them, because from there,
only the answer will be coming for any question given.
Okay, great.
Now the approach is going to be exactly same in a way that we know that route is here.
Okay.
So we have the route here.
We know we have the left subtree here again the left subtree here and the right subtree and the right
subtree okay.
So pretty sure we can draw each and every thing from this particular thing.
But let's now discuss that.
What are the left and right values are going to be?
Because if we calculate these values properly, then we can be sure that our tree will get created.
So left and right.
Great.
So what are the values which we have to calculate left in order start left in order end.
Left post order.
Start.
Left post order.
End.
Similarly.
Right in order.
Start.
Right in order end.
Right post order start and right post order.
End.
So if we are able to again just calculate these four values, we are sorted as of the root.
I think this is a lot clear to us that where root is?
Root is kept in the last element of my postorder.
So whatever array you are giving, giving me and I will have the length as well.
So from that I will just pick up my root as this.
So root we can very clearly write that it is postorder.
And n minus one.
Like I am taking the length as n and n minus one.
That is where we can get the root.
Again we will get the index.
So index of inorder root index okay.
So in order root index again we can easily find that given we have the root information from this we
just have to traverse this array and find out where my root is.
Okay.
So we are again taking not no duplicates because if duplicates are there then we have to discuss or
compare the address or the reference for my particular root instead of the value.
Great everyone.
So I hope each and everything should be clear.
Till now I'm not knowing how the tree will roll out that you have to do at your end so that the clear
is understanding is clear that how exactly this in order and post order will get divided.
The same thing which we did in inorder and pre-order.
Now let's see about the values that how exactly can we find out the values?
Okay, so pretty sure that till now everything is clear.
It is a lot parallel in the way we discuss the inorder and pre-order question.
Now let's talk about the exact values for left in order start.
I think it is in order start only.
Okay everyone, so we can see the same thing here as well.
This is my left subtree in order start great for the end of my in order, I think I can just directly
say that it is in order.
Root index minus one Okay.
Now let's talk about left post order start.
I think it is also straightforward in front of us.
It is exactly going to be where we have this particular start of the post order.
So I can say that it is post order start directly.
And now let's talk about where the left post order will end.
Now in this also we are going to apply the length because we know the length is going to be the same
for the left subtree.
And that overall formula which we applied that which I can write as well.
One second, let me write that formula down.
So left in order end minus left in order start is equals to left post order end minus left post order
start.
So I just have to send this particular term at this side and I will get my answer All right everyone.
So we are just discussing on the length given the length, because we know the length and the start,
we can find out where the end is going to be.
Again, very similar.
If you are standing at some position and you know how many steps you have to go forward, you can imagine,
or you can guess that where you are going to end up, right?
So on that note, I can just write it as left pre-order start.
That is where I will be starting, which is this particular position, a post order, not pre-order.
Sorry, this particular position.
I have this length as well, so let me just add it right.
So this will become left in order.
End minus left in order start.
Great.
So I think we have easily now based on our last understanding and overall post order, and in order
given, we can find out these four values.
Now let us talk about these four values for right.
Okay.
Now for right when I talk about right in order start.
I think we saw this in the last video as well.
How it is just after in order root index plus one.
So this is where my right in order is starting okay.
And we know the root index just the next index from it because that is how my in order is defined.
First the left subtree then the root and then the right subtree.
Okay.
Great.
So we can easily write it as.
In order root index and plus one.
Great.
Talking about the end it's again very easy.
It's the in order end wherever my in order is ending.
That is where I would say that this basically ends.
Okay everyone.
So I hope this is clear as well.
Now let's talk about right pre post order start right post order start I think it is here it is starting
from this particular position just before this.
We have the end as well left post order end, which we calculated here.
Right everyone.
So with this knowledge I can directly write left post order end plus one.
Okay so just I'm applying all I know.
So I know many of you might be feeling that there are lots of value to calculate, but what I will suggest
is just pause the video and try to draw the diagram as well as all this information and think at your
end once as well, that exactly where are we okay, and why are we finding all these four values for
each subtree.
And then try to see that okay, exactly where these values will be.
I'm pretty sure that you will get the hold of it.
This is the easiest way of doing this question.
Honestly, I'm not asking you to go into slicing calculate length in that way.
No, we are just making sure that by our understanding of how the inorder and the post-order starts,
we are able to get each and every thing.
Great.
Now lets talk about the right post-order end.
It ends here and I am always sure that if the post-order of right ends, then just the root is there
which is after it.
So what I can write here, it's the post-order end minus one one position for my root.
Okay, so I think yeah, we are just done with all the eight values which we have to calculate.
So if you are able to follow this properly, I'm pretty sure that you will be able to solve this question.
Now please make sure that you solve this particular question.
I have created a file.
So construct a tree from post-order and in-order.
Okay.
This is where we have to code this question.
This is also there on LeetCode.
Okay.
So again it's a leetcode medium question.
It is asked in lot of companies.
And again, the understanding is overall very much helpful in solving this question and other questions.
So what we can do is maybe we can just copy this only here, and you can complete this so that you will
get an idea about leetcode as well in general.
Right.
So what we can do here, we can just copy the LeetCode link.
And I would like you to just complete this particular file.
Let us actually copy the whole code.
So that refer it.
Yeah.
So you just have to complete this particular function.
Uh, I'm aware now I know that you are aware how we can make a helper function to do this.
So please try this at once at your end, everyone.
I'm pretty sure that you will be able to do this.
Okay?
So no need to.
I don't think it will be a problem now.
We have discussed the same in a lot of, uh, depth.
Just please make sure that you don't skip this and try to code this at your end.
Okay?
So thank you.
Let's meet in the next video.