Hi, everyone, welcome back.
So in this video, we are going to discuss about discussion and our travels and of accommodation.
So first of all, we know what is in traversal.
It is you visit the left subtree first, then you visit the note.
That is the data and then you visit denied Sabry.
So left and right.
And what is a Cartesian tree?
So it is a good indication that this tree is a tree in which.
Your route data will be the maximum data industry, so we have the subtree here, we have many nodes
here.
And so on.
This is one tree, and it is given that basically the road data route will be the greatest, it will
be the grid and all the elements and separate.
So route will be the maximum value.
And similarly, this property will hold for each and every node.
So for this node, this node will contain the largest data of all the elements in its separate.
Similarly for this node, similarly for this node.
So this note will contain the largest data among all its subtree.
So we are provided with these in order to have this tree.
We are provided with and love this tree and we want to construct that tree.
So given that traversal given the traversal it is left-to-right of this tree, we want to construct
this tree and it is given that duplicates will not be there.
So they are also providing us one example that if they are traversal is one, two and three, then this
will be your Cartesian tree that you can see.
Tree is basically larger than all the elements in the left and right.
Separate does not exist.
Similarly, element two is greater than all the elements in the left subtree and right separately for
two does not exist, and for one, left and right does not exist.
And the traversal for this will be one, two and three, which is correct.
We can easily solve this question with the help of recursion.
And in fact we have solved Tolkachev previously that given the order and the preordering reconstruct
the tree given in order in order to reconstruct the tree.
So this is going to be very similar to that only.
So what we'll do let's is the screen
and solving this problem is a cakewalk.
Let's take one big example.
Let's say I have this one, four, five, three, seven and nine.
Let's say I have this Eddie and let's say I have zero.
So all the elements are unique.
Duplicates are not pleasant.
And this is the trevathan traversal means left data.
And right now we want to construct the Cartesian tree for this.
So what will be our approach?
So first of all, we will try to find out the root data.
Right.
So what is the maximum value?
What is the maximum value?
Nine is the maximum value.
So that means nine will be my route, nine will be Darold.
Then this all elements, these all elements will be the part of left Sabry and these all elements will
be the part of Right.
Sabry So in the right we have only one node so we can connect this now.
Now let's talk about left.
So again what we will call recursion on this and the collocation on this.
So for this, what will happen again.
What we will try to find out.
The largest node, the largest node is seven to seven means seven will be the root node and all these
elements will be the left of seven and right of seven does not exist.
Right.
So this is seven data is seven, right.
Does not exist.
And all the elements left of seven will be a part of separate.
Again, industry five will be not because five is the maximum value.
So five will be the road and right of seven will be none were discussed.
Right.
So four, five, four and one will be in the left.
Three will be in the right sense.
In the right hand side.
We have only one node so we can construct one node.
Right.
And here we have two nodes.
So the maximum is for the maximum is four.
So four will be the data leftover will be delectability.
So this is the last of three or four and I have three or four does not exist.
So right.
Is null and in left we have only one in order.
So that will be this and this will be our Cartesian tree.
Very, very simple, right.
So we can see here, nine is bigger than all the elements in the left as well as right.
Similarly, we can check this for any node.
So I checking this for five.
So four five left values are less right.
Well you are also less.
And what will be the traversal.
So inheritance is left to right.
So this will be first of all, I will visit one, then I will visit four, then I will visit five,
then I will visit three, then visit seven, then nine and then zero.
Then seven, then nine and then zero.
Right.
So let's discuss the final approach, what we need to do.
So given this area, given the scenario, first of all, what I will do this is let's say I start.
This is legit, and so I will I read it from start to end and I will try to find out the maximum data
because the maximum data is going to be our root node.
So let's say this is the maximum data.
This is the maximum data.
So what I will do, I will create one node containing the maximum data and then I will call that it
goes in on the left hand side.
So this will be the part of Lexapro I will call recursion on right hand side.
These all elements will be the part of right subtree and how we can call.
So for calling on the left, I will update and to be the index for this, let's say max index.
So this really makes an X minus one and for calling on.
Right.
How will I call.
So this is Max Index and this is the value of start will be the maximum index plus one and that's it.
So this is going to be a recursive algorithm.
And I already informed you, what will be the recursive relation rate for calling on left?
This will be a start and this will be end for calling on, right.
This will be start and this will be the end.
Very simple code.
So you can try to write the code for this column yourself.
And the next video we will be writing the code.
So this is all over this device.
I will see you in the next one.
Thank you.