Hi, everyone.
So in this video, we are going to discuss the situation, reverse level order timeously.
OK, so this is very same this is very similar to the previous question.
Now, the only difference is basically I will perform the LEVEL-HEADED reversal.
We will perform the level traversal, but in reverse v..
OK, believer's I mean, from bottom to top.
Again, normal level is basically from top to bottom.
Reverse is basically from bottom to top.
OK, so what will be our output?
Consider this example.
So from bottom to top.
So seven.
Then I have nine and eight, so nine and then two and then so two and ten and then I have one, so basically
one.
OK, so this is the reverse level of the traversal.
I think about the logic.
OK, now consider this example, so it's traversal basically from top to down reverses, basically from
bottom to top.
OK, so from bottom.
So does this drill then?
I have tenanted, so I have 10 and eight, then I have 21 and seven, 21 and seven, and then I have
50.
So I have 50.
OK, very, very simple.
So this is the reverse level of the traversal.
OK, now let us see how we can.
So I'll just caution.
So this is going to be very similar approach.
OK, very similar approach we will take the help of.
We need you to perform the level of the traversal.
This is very simple.
We need you to perform diversity.
So apart from you, where do we lose?
We will use back to store our answer.
OK, Stack to store our answer, we will not likely print.
OK, so let us consider an example.
So this is, let's say five, 10, 12, seven and eight.
OK, so first let us write the simple logic code, simple level, whatever sort of simple level or traversal
says while your queue is not empty, you get a different element, you get a different element, you
bring different element.
And then if the left exist, push right, push left.
And similarly, you will check if right exist.
So Bush, right, this is simple level reversal from top to down.
OK, but here we have to perform the reverse level reversal.
So what we will do so instead of printing here.
Instead of the sprinting, what will look, we will store the answer in Stack.
We will store the answer in Steck, so basically if you perform the level, but I was a low key performance
level traversal, what will really bring to the value, OK, what will be the output if you perform
the simple laboratory?
So this will be five, then 10, 12 and then seven, eight.
OK, if you will print.
If I am printing.
So this will be five, then 10 and then one and then seven and eight.
And what I'm saying here is basically instead of printing stored it in the stack.
Store it in a stick.
So how will the store, first of all, five welcome, then 10, then 12, then seven and eight.
So basically this will be my steak.
Five, then 10, then 12, then seven and then eight.
OK, this will be Lastic.
OK, so when this loop will end, when the queue will become empty, so what I will write here, so
I will pop all the elements from the stack bop, all element from stack and print up.
All element from.
The Steck and Brent.
So every single element, so pop it and I pop seven, pop 12, pop, pop five, so this will be eight
seven, then I have 12, then I have 10 and then I have five.
OK, so this is basically the reverse level order traversal.
OK, now one thing, if you look carefully, it's the reverse order traversal is basically five, traversal
is basically seven, then it then 10, then 12 and then five.
But I'm getting answer wrong here.
Basically, eight and seven are slabbed.
Well, and then.
OK, if you will see, so basically this answer is wrong.
OK, so how we can make this answer correct?
How are we going to make this answer correct?
So basically, I will change this old.
I will change the order of these two lines.
OK, so at first I am checking if left exist, then Bush left.
So basically Ben is getting pushed first before 12.
But what I want I want to come first and then Ben.
So I will change this order.
So I will.
Right if right.
Exist then Bush.
Right.
If left exist, so Bush left, so after changing the order, after writing this quote, this output
will be changed to first five will welcome, then 12.
Well, welcome, then 10 will come, then it will come and the sound will come.
It is very simple.
So initially what I was checking first left existed, then Bush left.
But here what I will do first I will check.
Right.
So if will exist then Bush 12 first if left exist.
So then Bush left.
If right to exist then Bush right.
If left exist then Bush left.
OK, so basically I will change the order.
OK, so this will be my new order.
So if this is my new order, this will be my new output, this will be my new output.
And if I will store this output in stack, if I was told this output instead it will be five, then
12, then ten, then eight and then seven.
OK, and if I will pop every single element from the stack, bop every single element from the stack,
so it will be seven, eight, 10, 12 and five.
OK, so it will be seven, eight, 10, 12 and five.
OK, this is the right answer.
You can compare.
OK, you can compare.
So what we have to do, we have to do minor, minor changes.
So what is a minor changes first, instead of printing the value, what I will do, I will store it
in a stack.
This is the first change that we have to do.
Second change is basically I have to reverse the order.
I have to reverse this order.
First I will check for right, then I will check for left.
OK, so this is the second change, 13, just basically when the queues empty, all the elements are
basically present inside the stack.
So what you have to do.
You have to pop all the elements from the stack and then print.
OK, so basically what will be the time and the space complexity?
So again, the time complexity is big.
Often we are just iterating over all the nodes and space complexities big, often for queue and big
often for Steg.
So ultimately the time and the space complexity, they both seem, they both are big, often OK.
They both are big often.
So I hope you understood the logic and the question.
OK, so now let's write the code, OK?
So here this is the binded trailer traversal part two.
OK, this is called in reverse order traversal bottom up level.
Order traversal.
OK.
So basically what we have to do, so this is the second part of the question, this is a reversal of
that reversal, but according to the question, they are calling it a bottom up level reversal.
OK, what are some bottom up level traversal level order will now see?
So if this is the input, this is my output first 15 and 17, nine and 20 and then three.
OK.
But if you will recall from the last problem, what is our output, so we are storing the output in
this very first level one.
Then level two.
Nine and 20, and then I'm starting level three, which is 15 and seven.
So if I will ride my old cold, OK, so this is the output.
This is the output from our last call, from our last problem.
OK, this is the output from our last problem and if you will compare.
So basically this output is just the reverse.
OK, so what we will do, I will write the old code, OK, we will use our old code and just we will
reverse our output.
OK, so reverse our oil output.
It was all output and you will get the new output, you will get the new output.
So after reversing this, after reversing this, 15 and seven will come along.
Then I have nine and twenty and then three will come.
OK, so here in this question, what we have to do, our old output, our old code, and just we will
use reverse function.
OK, now let's see.
So basically, this is the old question, this is this simple traversal, OK, this is the old question.
What will letters copy, the so-called.
Let's copy this code and let's it hit.
OK, so this is our old code and what we have written, so instead of returning normal answered.
What we have to do, we have to reverse our output, so let us so reverses in malfunction.
It will take two things as inputs starting and end.
So starting is we not begin.
These starting my output.
So starting will be the dowbiggin ending will be redundant.
OK, so this liver function will take two things from two things, OK, from where to where I have to
reverse.
So basically, this reverse function, this reverse function.
It takes tooting the starting point and the ending point, OK?
For example, you have let's say you have a string, very large string.
So you have to give from where to where you have to go from here to here.
You have to reverse or from starting to at the end.
OK, so I want to reverse my hole that I want to reverse my whole vector.
So vidauban mean the starting point without end means the ending point shaft reversing our logic and
our colistin, I will likely return.
OK, now one interesting thing.
See, the level of discussion is basically easy one and the previous quotient at that level was medium.
OK, so this is like very funny.
So our work is done.
I have to just write this line and now let us submit our good.
OK, so our court is working now.
So this is basically execution and this is basically medium question.
So like this is like really funny.
OK, so if you have any doubt, you can ask me.
OK, thank you.