Hi, everyone.
So in this video, we are going to solve another question, so we have to construct adultry given the
preorder traversal and reversal of that.
So, for example, this is the product reversal of a tree and this is the reversal of a tree.
And it is obvious that the number of elements will be same.
So given preorder and traversal, we need to construct this tree.
So for distri, this will be my preorder traversal and this will be my traversal.
So basically the input which we are provided is basically the pre order and in order sell and we need
to construct a battery and we need to return the root.
So how we can solve this question, so it's very simple, what is the traversal?
So preordering first day to basically root node, then Brenda left subtree and then print the right
subtree.
And what is the traversal, so in order, first print delectably, then print the road, so then print
the data and then print the right separate.
So first of all, in order to create this tree, I need to identify what is the root, so for finding
out the root.
We know the first element in the traversal is the root.
So tree is the root.
So tree root.
Now, various three percent in the Ed Salvatore's present here, so that means this will be the left
subtree and this is the right side because you can see data.
So before data, we have delectably and after data we have the right subtree.
So that means nine belongs to the left subtree and 15, 20 and seven.
So this belongs to the right subtree.
Simple.
So first step is done.
Now, what will do?
We will collocation on the left subtree and we will collocation on the right subtree.
So far left Sabrin since there is only one node.
So what will be my output.
Simply three and nine because there is only one node.
Now let's discuss for the right subtree.
So 15, 20 and seven.
So this is the right subtree.
15 twenty seven.
And similarly these are the elements 15, 20 and seven.
So this is the broader traversal for the right subtree and this is the in order traversal for the right
subtree.
Now I need to find out the root for the right subtree and various root present.
The first element.
So 20 is the first element.
So 20 now versus 20 present in the traversal.
So 15 will be the last three, because we know when you will print the data in the in order to give
us a left before data, we have left subtree after data we have right.
So 15 is basically the left subtree.
Seven is the right subtree.
So seven is the right subtree since this is a left and right.
But there is only one node.
So this will be my dream.
2010, 15 and then seven.
So you can imagine how.
So that's how you will be able to solve this question.
So what you need to identify, you need to identify what is the right subtree, sorry, what is the
right product reversal and what is the right in order traversal?
Similarly, what is the left preorder traversal and what is left in order traversal?
Let's take one more example.
So this is an example.
So given the traversal and given the traversal, we need to construct a district.
So just remember in the traversal.
So if this is the area of DiPiero Trevathan, first you will print the data.
Then you print the left subtree.
And then you print the right subtree.
And what is in order to save this is the area which is containing the traversal so deeply traversal
area, so these two areas will be of the same size.
So in order traversal first, we print the subtree.
Then we print the root data, then we print the right subtree.
So this is route data.
So let's see how we can solve this question, so first of all, I need to construct this tree and I
need to return the root.
So there is root.
Root is the first element of DiPiero traversal.
So one is the root.
So when is the root?
Now let's find the root in the traversal.
So we will find this data in the traversal so that we can know what is the of and what is the right
subtree.
So we will find one in the traversal.
So this is one.
So that means this is the left subtree and this is the right subtree.
So basically for to belong to left subtree and seven five eight three six belongs to the right subtree.
Simple, so you can see four and two are in delectably and this seven, five, three, six, eight.
This is the subtree.
So now what we will do, we will do exactly the same thing.
So we will call for the left subtree.
We will call the kitchen on the right.
So this tree will be built and it will build this tree.
Also simple.
So for foreign to what we will also for Oriental here.
So this is left in order traversal.
See if you want to build a tree, if you want to build a tree, you need deep water traversal and you
need the traversal.
Now, I want to build the left a tree.
I want to build a tree.
So that means I need left in order traversal and I need left preorder traversal simple.
So what is recursion indication?
What regulation will do?
We will give small, we will give smaller size and same problem.
So the question will solve smaller size problem, but the nature of the problem will be seen.
So what is the big problem?
Big problem is given the bureau traversal of the entire tree, given the diversity of the entire tree
and we need to construct the entire tree.
But here, what is our problem?
We need to build the left subtree only, so we need a left in order to sell and we need left preorder
traversal simple.
So again, the problem is same now.
So this is the first element.
That means this is the root.
Root is the first element.
So that means for the left, Sabry, who is the root?
And so to search two here and four four is basically delectably four will come on the left.
So my left part is complete.
Left is one, two and four.
Now, let's discuss about this, so this is the now I want to build the right subtree, so this is right
in order traversal and this is right preorder traversal.
So this is right preorder traversal.
So we need to construct the route.
What is the route three is the route because in the first element is the route.
So trace route.
So I will search for three here.
So this is the left subtree of three.
This is the right subtree of three.
So I have three here now for the left subtree.
I have seven, five and eight.
This is the left subtree and what is the right subtree of three, right, subtractive six.
You can see this is the three of three and this is the right subtree.
So if there is only one road in the right subtree, we can likely use this three arrows.
So this is complete.
Now we want to discuss how we can build a factory so far building the left subtree.
You need the left to be order traversal.
So this is the left in order traversal and this is the left preorder traversal.
So the first node is basically the root node.
So five is the root node.
So we will search five here.
Seven is in the left, it is in the right.
So seven that left it in the right.
So now my dream is complete and we will attach all the parts.
So what do we have here?
So I have one.
So I have one now, four and two in the left.
So we discussed this is the.
So this is true.
And this is for and we discussed all these elements and.
Right.
So tree is the root, nor is the root, nor in the root of tree.
We have six and four.
These three elements we have discussed.
This is the tree.
So five then seven.
And then.
So now let's match.
So basically, if you will match these two are exactly the same.
So I have one here, one, two and four, then three, five, six, seven, eight, three, five, six,
seven and eight.
So this is how you will be able to solve the problem.
Now let's discuss.
How we can solve this problem.
So basically.
This is in traversal.
And we have traversal, so traversal is Zanardi.
Fyodor Traversal is also an area.
So first, we will bring the left subtree, then we will print the data and then we will print the right
subtree.
And what is the traversal first, you will print that data.
Then you will bring the left subtree and then you will bring the right subtree.
OK, so one question.
So can we build a tree only with the help of another traversal, so, for example, if this is my traversal
120, so what Maitri so I can construct two tree.
So first one is basically like this one, two and three, and the second tree can be one, two and three.
So both the trees are possible.
OK, so if only traversal is given, you can construct the industry and you can also construct of this
tree.
But I want uniquely, I want that my output, my tree should be unique.
So that's why we need Bearder traversal also.
So that's why we need to traversal OK two different Everson's so we can construct tree with the help
of in order.
But that tree will not be unique.
But since I want the unique tree.
So that's why we need the tree also.
So now let's discuss how we can construct that.
So what I will do, I will construct truth, so I will construct the truth and then what I will do.
So I will build the left subtree recursively and I will build the right subtree recursively.
So what is the solution?
I will construct the root node.
I will construct the note not and the coalition will build the left and the right.
OK, so what is the root node?
Root node is basically the first element for constructing the root.
We should note what is the data?
And we know that the data is basically the first element of deputed trevathan so we can easily construct
our own.
Now let's discuss how we can build our left and right subtree.
So what is the problem?
I want to build a tree now for building the tree I need in order traversal and I need to build a traversal.
Now I want to construct the left Sabry.
I want to construct this left subtree, so for constructing this left subtree, I need left in order
traversal and I need left preorder traversal.
So that is the property of recursion.
Right.
So this is the big problem and this is the smaller problem.
So the input size is smaller, but the problem nature is exactly the same.
Now let's see how we can build our lives.
Separate recursively.
So left in order traversal, so for finding the left traversal.
So this is my left in order to listen what I need, I need left in order to start.
And I need left in order.
And so these are indexed left in order to start the next level in order and index.
Similarly, I need left preorder, so I need left preorder starting next and I need left preorder and
index.
So this is what does this.
So this is preorder starting next for the entire day.
This is the preorder and index for the entire trip.
This is the in order starting next for the entire tree.
This is the in order and index for the entire tree.
So if basically, let's say the number of elements are five.
So what is to start?
It is zero.
What is the.
It is basically the first index of the original with the last index of the total number of elements
are five.
So last and next will be four.
So this is your next four and this is your next four.
So I want to left in order that I want left in order.
That means I want to know what is the starting next, what is the ending index?
Similarly for the left preorder area, I need what is the starting next and what is the ending index
and how we can find out this.
So it's very simple what is left in order to start.
So this is the left, so left in order to start this same as in order to start.
So left in order to start is same as the start.
What is left in order and so this is left in order and I don't know what is this index?
So we'll discuss it later.
What is left preorders.
Right.
So this is your start and plus one.
So preorders start.
There's only one element, right?
There's only one element.
So this is the left before the start.
So this is simply preorders start plus one.
Just the next element of the root element.
Simple.
So now let's discuss how we can find out the left in order to end.
OK, so one thing, you know, what is the root element?
You know, the root element.
So you will search this root data in the US and you will light it and then you will search the data.
Let's say the name of this index is root index.
So what is left in order?
So this is the left in order, and that is rootin X minus one.
So this is Rudy Index.
Minus one simple.
This is Rudy, the next you will find out the Rudy next just by iterating over traversal and he will
match the.
So where does my left end?
Just before the Rudy index.
So this is the left hand.
So now let's discuss how we can find out the left preordering.
OK, so one thing, the number of elements will be seen, right?
So a number of elements will be same.
That means left.
So this is left in order and minus left in order to start will be same as left preorder and minus left
preorder start.
So what does this value?
This value is basically the number of elements in the left subtree, number of elements in left subtree.
So a number of elements in the left is going to be same, right?
So this is also the number of elements in the left subtree.
So that's why these two are equals.
So now I know Disvalue.
I know Disvalue.
So I have calculated this value here.
I know Disvalue, so this is the value.
I also know Disvalue, you can see I also know Disvalue, I just need to find out D'Israeli.
So this is an equation which is containing four variables and I know the values of three variables,
disvalue, so disvalue this and this value so we can find out disvalue easily.
And what is this value?
So let's put the value here.
So this is we will take it to the left hand side.
So this is left in order and minus left in order to start.
Plus, left preorder the start, so this is that simple.
So now we will be able to construct our left sabari.
Now we will do exactly the same for the rights of also.
So we need for building the right subtree.
I want to build.
So I want to build the right subtree.
So for building the right subtree, I should know what is the right in order traversal and what is the
right preorder traversal simple so far, right in order traversal.
I need right in order starting next.
And I need right in order and similarly, I need right preorder starting next, I need a right preorder
and indexed simple.
So this is my Doretti.
So first we opened the left subtree.
Then we print the root node and then we print the right subtree.
And what is border?
So for preorder, first we print the root node.
Then we print the left subtree and then we print the right subtree, so let's try to find out these
four values.
So this is in order to start this is in order.
And this is.
Preorder and this is preorder starting next.
So what is right in order starting next?
So in order right, I want to find out this index starting index and we can easily find out this how
you know, the route you will search, you will find out the index.
So I am calling this index is route index and this index is just one next.
So this is route index plus one.
This is Rudy Index plus one, so this is just the next element of the rudiment.
And what is right in order and so right in the end is same as in order.
And so this is the same as in order.
Now let's discuss right from the start.
So.
Right.
So this is right.
And we need to find out this element, the starting element.
So we have already calculated the left.
So if you remember, we have already calculated the left pre order and in just above and we will do
plus one.
So we calculated this value for the left right.
If you remember, we need to do plus one to find out the starting next for the right and what is right
preorder.
And so the same as preordering.
OK, so now we know all that eight values, so you need to find out your values, so for values, for
the right subtree, these four values, and you need to find out these four values.
For the left subtree, for building the left sempre, if you will be able to find out all these values
easily, then you can easily construct your tree and what will be our function.
So our function will take input.
So our function will take as input, preordering ourselves input in order to start in order and preorder,
start pre order.
And so this is how our function will look like, OK, in order to sell the starting next in order and
index preorder starting next, preorder any next.
And we calculated all day values so that we can call on the left Sabry and we can also call them the
right Sabry.
So now I think you will be able to solve this question.
So this question is basically President netcode.
So what I want you guys to do is so first of all try to write the code for this problem yourself and
in the next we do, I will write the code.
So I will discuss the solution, I will write the code in the next renewal.
And first, you should give it a try.
So this is it from this review.
I will see you in the next one.