Hi, everyone.
So in this video, we are going to discuss about the vertical ordered reversal of a binary tree, so
what is a vertical ordered reversal?
So we can understand this with the help of an example.
So let's talk about this example.
Right.
So let me try it here.
So I have three, then I have nine, and then I have 20.
So this is 15.
And then I have seven, right, so this is the tree and what happens in vertical reversal is basically
this let me change the color.
So see, this is one line.
We are traversing the tree vertically.
Second line.
Third line.
And fourth line, so in the first line, nine is present in the second lengthy and 59 percent, three
and 15 in the third line, I have 20 and in the fourth line I have seven.
So that is the output.
So we need to traverse that three vertically.
We want to traverse the tree vertically.
Let's take one more example so that you can understand it better.
Let's talk about this example.
So here, let me draw that tree.
So I have one, then I have to.
And here I have three.
So here I have four.
Here I have five.
Then I have six here and then I have seven here.
So again, we will do we will draw the vertical line.
So one vertical line and they will decline another vertical line, another and the last one.
So on the first vertical line I have four.
On the second vertical line I have two.
On the third vertical line I have three elements, one, five and six.
So I have three elements, one, five and six.
On the fourth vertical line, I have only one entry.
And here I have only one element, which is seven.
And that is your output.
Right.
Let's take one more example.
So I think they have provided.
So we have one more example.
And again, let's not agree.
So I have one here, then I have two.
Then I have four.
Then I have six here.
So I have three here, I have five here and I have seven here.
And now let's draw the vertical lines.
First vertical line, second vertical line tower vertical line.
Fourth vertical line and fifth vertical line.
So on the first vertical line, I have only one element, and it is four on the second vertical line,
I have only one element, that is two.
On the third vertical line, I have three elements, one, six and five.
And here I have elementary and here I have elements seven.
So if you really compare these two, so the only thing that is different is basically this one.
So here this thing went five, six and I am writing one six five.
So it is given in the question, in the question.
They are saying that when you're returning the output, return the output unsorted a minute.
So what will do before returning the answer?
So before returning the answer, we will start each and every element.
So it is containing one element.
So don't do anything, one element, don't do anything.
And here it is containing more than one element.
So we will start and then we will return three and seven.
Right.
So days when one element or nothing.
So don't need to do anything.
So this extra thing that is unit to return, you are put in a certain amount.
This is given in the equation.
So that's why before returning the answer one six five, I will start and then I will return one five
six.
So I hope you have understood what is particularly traversal right.
This thing is clear to you now.
So now the question comes how we can solve this problem.
So what I will do I will explain you everything in this video and you will try to write the code yourself.
And in the next video, we will be writing the code.
So what will happen?
The logic to solve this problem is really, really very simple.
So what they will do, so let me do one thing, I have three here, let me try again.
Nine, I have 20 here, I have 15 here and I have seven here.
So I will create one map.
So this map will be horizontal distance versus list.
So horizontal distance will be one integer and list, obviously, you need to create one array or create
one vector list, right?
So this will be my key and this will be my value.
So what is this horizontal distance?
Let me explain you.
What do I mean by horizontal distance?
So a root node, horizontal distance, zero.
So whenever you will go left, you will reduce horizontal distance that is horizontal distance, minus
minus.
And whenever you will go right, you will go horizontal distance plus place.
So let's do with me.
This is three in and I am going left.
So horizontal distance for this is minus one.
Let's go here.
So from zero horizontal distance plus plus horizontal distance is one.
If I will go right again then horizontal distance plus plus lattice or the distance will become two.
So if I will go here then I'm going left.
Degrees.
So from when the horizontal distance will become zero.
So now we're going to do so for this node.
The horizontal distance is minus one.
So I was told in a map like this horizontal distance minus one, and I have only one node whose horizontal
distances minus one.
Now let's talk about zero before zero.
I have actually two nodes.
This is the first node, which is horizontal distance and zero.
And for this note, also horizontal distance zero.
So I will write three and 15 here now, horizontal distance one.
So I have horizontal distance one and only one node.
Again, I have horizontal distance two and the node is seven.
Right.
So your map will be ready and how you can prepare this map.
So what to do?
You need to do level order traversal.
You will do level order traversal and after doing the level order traversal your map will be ready and
for doing traversal what we need, we need when you.
So earlier, we used to have you of note, right, we only saw the note, but right now we noticed two
things will to the node as well as the horizontal distance.
So you will store two things.
It will store your node and it will store your horizontal distance.
So what you can do, you can make one class that is containing these two variables.
So after doing the level traversal with the help of your map will be ready.
Your map will be ready and then what do you need to iterate over the map, you will.
So the first value is nine, so you will put the answer that the answer is nine.
Now, the next is three and 15.
So the next is three and 15.
The next one is 20.
So you will put 20.
The next one is seven.
So you will put seven.
And that is your answer, right.
So what do you need to return a unit to return vector of veteran teachers?
So this is a vector of individuals, vector of integers, integers, vector of integers and a big vector.
But that's how you can solve this question.
You just need to do traversal and fordoing level or traversal unit to store two things node as well
as the horizontal distance.
And then your map will contain horizontal distance to basically list of nodes that are corresponding
to this horizontal distance.
So let me take one more example.
And to make myself clear, let me draw the tree again, so I have one here, then two, then four,
then I have five here, so I have three here, I have seven here, sorry, six here and I have seven
here.
Now, again, horizontal distance is zero.
I'm going left.
So for this minus I'm going left for this minus two I'm going right.
So it will become zero.
I'm going right.
So it will increase.
I'm going right.
It will increase.
I'm going left.
It will decrease.
So now we have the horizontal distance for every node.
Right.
So when we are doing level traversal we will prepare the map.
And in this map, we will have horizontal distance to the list of nodes, so horizontal distance four
minus two, so four minus two, I have only one node, which is four for central distance, minus one.
I have only one node, which is two.
Four zero.
I have three nodes, actually, this node, this node and this node.
So one, five and six for this horizontal distance one I have only one node, which is three for horizontal
distance two.
I have only one node, which is seven.
So by doing the level of the traversal, you will be able to prepare this map.
You will be able to populate this map.
And once your map is ready, you need to iterate over your map.
You will read all the map and we have the answer.
So first is for you can see for next is two.
So I have two here.
Next is one, five, six.
So I have one.
Five, six.
Next three.
I have three.
Nexus seven.
So I have seven.
So basically this approach is going to work.
Very easy question.
You just need to do order traversal and while doing the level traversal the cuvee start putting it to
the node and it will store the horizontal distance for that node.
And then you need to do simple level or traversal and it will insert the values in the map.
And once the level traversal is completed, you need to redraw the map and you need to populate your
answer.
Very simple logic.
And the code is also going to be very, very simple, if you will follow each and every step.
So in the next video, we will be writing the code for this problem.
And I will see you in the next one.
Thank you.