Hi, everyone.
So in this video, we are going to discuss what is Lawanda traversal of a tree?
OK, let's take an example.
So consider this example.
OK, so law and order means we will traverse level, right?
So this is level one.
Its output is one.
This is level two.
Output of level two is the entry.
This is level three.
So the output is four five.
OK, very, very simple.
We are just traversing level rise, level one, level two and then level three.
OK, so for this tree, this is my level or that level said one, two, three, four, five.
Now let us consider this string and let us try to find out its level or traversal.
OK, so level one.
Now, level to nine and 20, then level three, so this is 15 and seven.
OK, so this is the level of the traversal for this ministry.
OK, very, very simple.
We will just reverse the train level, right?
OK.
Was the tree level right now at this example.
OK, so this is level one seven.
Now this is level two, then in 15.
Now this is my level three.
OK, 15 and 30.
Now this is my level four.
So its output is seven.
OK.
So this is the level where the driver said, look, this is the level driver for this by Nutri.
OK, so I hope you understood what is the meaning of leveland traversal.
Now let's discuss how we can find out the Labrador retriever Saluki, what will be our approach?
So let's first consider an example.
OK.
So I suppose this is a binary tree.
OK, we will try to find out the Leonard traversal for distri, so our approach is very simple to find
out the level of traversal we need UCU.
OK, and now let's see how we can use to find the level traversal.
So the approach is going to be very, very simple.
OK, so what we will do, we will construct a queue.
OK, so let's make a queue.
So initially the queue will be empty.
OK, initially the queue is empty, then what I will do, I will push the root node inside the queue,
OK, so push the root node inside the queue.
Now here I will write my output, OK?
Now, what I will do so I will pop the top element of the gloom.
I will pop different element of the gear and I will print.
So I will print to not after printing, too, I will check.
So the left subtree of to exist, that is three.
So Bush three inside the key.
OK, now Bush three inside the Q similarly check the rates are pretty of to exist.
Yes four exist.
So push for inside the Q.
OK, now, next step again, Bob, a different element of the queue.
OK, so this is three.
After popping, I will print.
So I am printing three.
Now, after printing three, I will check so left off three exist.
Yes, it is five.
So Bush five.
Right off three exists, it is estriol, so I will push Tooele.
Very simple.
OK, now what I will do, I will pop different element.
So this is for.
And Brentford now, after printing for Jack, the left of Ford exist, it does not exist, so do nothing.
Now, check the right of what exists, it exists at this point, so I will push down inside the queue.
OK, so now, Bob, different.
So this is five.
And print five year now after printing five jec so left of five exist, no right of five exists.
It is eight, so push it.
Very simple now, Bob, different elements, so this is.
OK, so I will print will.
Now, check so left off it will exist, no right of tool exists if it exists BUSH So I will push inside
the queue.
Again, I will pop different element.
And I will print it here.
OK, now check for 10.
So this is my pen left off don't exist.
No right of existence.
So do not push anything inside the cube, OK?
Now let's pop it so it will come out.
So this is my ID.
OK, now check left of it exists.
So push nine.
Right off it exist, doesn't it does not exist, so do nothing.
OK, now let's pop this element.
So this is seven.
So right, seven hit now check left of seven exist, no right of seven exertional, so do nothing.
Do not push anything inside the queue.
OK, now pop this element nine.
And printed here.
OK, so left of nine exist, no right of nine exist, no.
So basically do nothing.
Now our queue is empty.
OK, so our queue is empty.
So when our two will become empty, we will stop.
And this is my answer.
This is my level of traversal.
OK, you can see I have two, then three, four, then five to 10, then I have eight and seven and
then I have nine.
OK, so basically our output is correct.
It is hundred percent correct.
OK, so you can see with the help of you, we can easily solved this question.
OK, we can very easily solve this question.
Now let us take one more example to understand it in a better way.
OK, now this time we will take a small example.
Look.
So let's say this is my small example.
OK, so this is a very small example, so initially what we will do, we will construct queue, we will
make a queue.
And our goal will be initially empty.
OK, I would give will be initially empty.
And I will ride my outputted.
So approach is very, very simple to do so initially, I have to put initially I have to push the root
element.
Okay, so I will push to.
Now, let's start so what I will do, I will pop the element.
OK.
So first step is take a different element of the queue.
So this is the first step.
Find out different element.
And this volume outputs right through here.
Now check.
So left off to exist yesterday exist.
So push three.
OK, so second step is, if left exist, then Bush left.
OK, so if left exist, then Bush.
Now for to write also exist, so I will also push forward.
OK, so push for the third step is right exist.
So if right exist, then Bush.
OK, so what I will do after this.
I will pop three, OK, again, different element.
Step one, again, different elements, so I will write three here now.
So left of three exists, five exist.
So push five.
No check for right of pre-exist, no, it doesn't exist, so do nothing.
OK, now, Bob, this element, Bob, different elements of the cessford.
Now check so left of what exist.
No right to exist.
Yes.
So Bush six.
Very simple, then again, a different element printed here.
Now, Jack left of five exist and no right of five exist and also do nothing now pop this element.
So this is six so left of six existing, right of six existing and also do nothing.
OK, and finally, our goal will become empty and we will stop.
And this is my answer.
Two, three, four, five, six.
You can see our answer is right.
Two, three, four, five, six.
OK, so our answer is right.
So these are very three simple steps that we have to perform.
OK.
So what will be our gold, silver, gold is going to look, our gold is going to look very, very simple.
OK, so what will be our gold and what we will do?
So first of all, there will be a loop and it will run while the queue is not empty.
OK, while the queue is not empty.
So what I will do pop different element of the queue.
OK, so basically pop front element of the queue from the front element, then what will do so if left
exist.
So if left exist then push left inside queue, then Bush left inside the queue.
And similarly if the right exist then push right inside the queue, then push right inside the queue.
And this is the complete hold.
OK, so this is the complete gold.
Now, let us modify our question.
OK, so basically suppose now what I was printing initially, so suppose this is the tree.
Now, in which order I am printing, so I am printing like one, then I am printing two three, then
I am printing for five.
OK, so with this logic I can print, I can print like this.
With this logic, I can print like this, but I don't want to print it like this, I want to print it
like this one, then in the next line to comadre, then the next line for Komova if OK, you got me.
I do not want to print like this.
If I want to print like this, then this court will work.
This is a hundred percent correct, but I want to print it like this in the next line.
OK, so first the output of level one, then the output of level to the output of level, then the output
of level four in this way.
OK, so this is the output of level one.
This is the output of level two and this is the output of level three.
OK, so I think you got me how I want to print out and said, OK, now what we will do.
So we will modify the school, we will modify this code and let's see how we will modify the school.
OK, so we will take the help of an.
Now let's see how it will help us.
OK, let's try to find out how it will help us.
So let us take an example.
OK, so suppose this is Maitri.
OK, so what we will do, so let us follow our old approach so our old approaches make UCU.
And initially, our car will be empty.
OK?
So initially, our goal is going to be empty.
OK, so I will ride my outputted.
Now, what we will do so our all approaches Bush, too, so this is the old approach Bush to now the
new approach, says Bush also.
So I will push two things, I will push two things.
First is the basically the root node and second one is basically the null.
Correct.
And I am pushing to think, OK, then we will follow our standard approach.
OK, what is the standard approach?
So Pop, different element right here.
OK, then, after popping the element I will check left exist.
Yes, Bush three, right exist.
Yes, Bush then.
So this is the standard, our old approach.
OK, now Bush, different element, OK, Bush, different elements.
So this time this element personal.
OK, so this is the special case.
This is a special case we are pushing.
OK, so we are getting well.
OK, different analyst Besant.
So when we are popping then so that is a special case.
So I will check after popping out.
Is that empty.
So specialist check.
So after popping, after popping Nele if you is empty.
If go empty, then do nothing, if Grandpre, then do nothing but if.
But if CU is not empty, if not empty, then what we will do, then we will.
Bushnell.
We will push none again.
OK, so in this case, let us know, so is the Green Party.
No, it is containing two elements three and then OK, this containing two elements.
Or if the key is not temporary, I will.
Bushnell So let us Bushnell.
So I will Bushnell.
OK, so now let us pop the next element, so this element is basically three, so.
Right, three in the next lane.
OK, so whenever you are encountering a lull, OK, whenever we face and what we will do, I will write
out, OK, so whenever I am encountering and I will do two things.
First thing, what I will do, I will ride out and line.
Whenever we encounter first Tengiz Singleton line and the second thing is basically we will decide between
these two.
OK, now, after popping out three check, so left exist, yes, right exist, yes, so Bush five and
four.
Again, Bob, then right down here, left exist, no right exist.
Yes, so Bush will Bush to will again be in control.
As soon as we encounter what we will do, our first step is basically leveland so I will go ahead.
Now, a second step is if goo is not empty, then Bushnell again, so I will push again.
So I have none again.
OK.
Now, different elements of this is five, so right, five here, not left exist, yes, right exist.
And so Bush 15.
Then pop the front element.
This is for the right for here now, now check left exist, no right exist and also do nothing.
OK, now I have to.
OK, so basically right now a chick left existence right exists.
So Bush 13 and 17.
Now, again, we are in control, so as soon as you can control, I will go to next lane and then check
if the queue is not empty.
Bushnell again, so queue is not empty, I will push again.
OK, so now what?
Fifteen and right, fifteen here now, Jack, left, no right exist.
Yes.
So Bush 18.
So push it in.
Now, check now 13.
OK, so right, 13 here left exist, no right exist, no do nothing.
Now, pop 17 right.
17 here left exist.
No right exist.
No do nothing.
No pop none.
OK, so after popping out what do do.
I will go to next lane.
This is the first to step.
First step is basically go to the next lane and now check if goo is not empty push again.
So I will push monologuing.
Now, Bob, differently when this is 18, so right, 18 here left exist, no right exist, no.
Then do nothing then Bob differently.
So this isn't as soon as going to go to the next step and then check.
So in this case goes empty.
If you is empty, do nothing.
Do nothing.
OK, and finally, what will happen.
Our school becomes empty now our queue is empty.
So when the queue will become empty, we are done.
We will stop.
And this is my answer.
This is my answer, which is 100 percent correct.
OK, we are operating level, right?
So this is output of level one.
This is output of level two, output, level three, four and five.
OK, so what is that?
What is like Vivyan Lucindale.
So signal is used to differentiate between levels nahles used to differentiate between levels.
OK, so basically as soon as you can control, as soon as you encounter, that means one level has finished.
OK, so as soon as we encounter Annell, that means the current level has finished.
Current level has finished.
OK, very, very simple.
So how we can modify this so-called.
So what we will do so we will modified this code here, we will write a special condition, what will
a special condition.
So basically when I am popping different element, I will check.
So if different element.
It's basically a null character, then our first step is to basically print and then basically go to
the next line.
And the second step is basically I will decide whether I have to Bushnell or do not.
Bushnell OK, if the kill.
So basically, if the queue is not empty, then I will.
Bushnell If that is temporary then do not.
Bushnell.
Very, very simple.
OK, so vinyl used so nahles used to basically it is used to differentiate between the levels.
So as soon as you will encounter a character that means the current level has finished.
If the current level has finished to basically go to the next level, go to the next level.
OK, very simple.
Now, let us take one more example to help you understand it better, OK, this time we will take a
small example.
So two, three, 10 and 12.
OK, so this is Mitry.
So what I will do, I will make UCU initially.
I will will be empty now.
I will push two things.
I will push route.
I will push a null corrector.
Very simple.
Now, I will write my output here, so, Bob, different elements, the system now left exist.
Yes, right exist.
Yes.
So push three and then push three and then.
OK, now, Bob, the next element, so this isn't all, so as soon as control the current level is finished,
go to the next level.
And if the queue is not empty, Bush again.
So it is not pretty.
I am pushing their luck in.
Now, Bob, different elements of the story, so right here left exist, no right exist, no do nothing
but a different element.
So this cistern left exist.
No right exists.
So Bush will Bush will now be optional.
So as soon as he can control the current level is finished and go to the next level, do is not empty.
So Bush again.
We will push again.
OK, now, Popplewell, right, well, here, left existant, all right, existential.
Now, pop, again, go to the next level now, this time the queue is empty, if it goes empty, do
not push again.
So finally our queue is empty and we will stop.
And this is my answer.
So this is level one, this is level two, and this is level three.
OK, so our output is right now, it seems to have understood the logic.
I think now is the time to write the code.
OK, so let's write the code.
OK, so this is the question that I was in, so in this question, we do not have to print anything.
Basically I have to return.
OK, how we can return.
So basically, you can see the return type of the function is basically the private property.
Just so basically these are truly free.
So you can see the output.
This is level one.
So I am printing three here now, level two.
So this is level two and this is level three.
So this is level three.
OK, so that part of the property.
So this is a vector of integers.
This is also a matter of intelligence and this is a vector of intelligence, and finally I have a bigger
one.
Basically, it is a tool that I have to return to the area.
OK.
And input is basically the three.
OK, so now let's write the good.
So first, let us create our answer, OK, so our answer is basically a Tooryalai.
So vector of vector of integers, let's name it.
OK, we will be my answer.
Initially it is empty.
And now let us create.
I've had third temp, OK, because to push anything inside this vector, I have to push a vector.
OK, so I will push this temp vector.
So this is initially empty.
OK, now what we have to do, I have to make a queue.
OK, step one.
So let us right the step and then we will follow the steps.
So the steps are very simple.
So step one is basically make UCU.
McHugh and Bush do things, so I will push two things.
So first thing is basically I will push a node and second thing is basically I will push the null character.
OK, second step is basically I have to use a loop.
So while the queue is not empty, I have to bend.
So I do not have to print in this question.
I have to store and then I have to return.
OK, so what will do, get the top element.
OK, so get a friend element of the queue.
Get different element of the queue.
Now here I have two conditions.
So if the front element is null.
The front element can be different elements, well, that means the current level has been finished,
so I have to do two things.
So first, things basically go to the next level.
So I will look out and learn.
And after doing this, I have two options, which again, do not Bushnell again.
OK, so do not.
Bushnell.
Bushnell We will.
Bushnell if the queue is not empty, if you not and then Bushnell otherwise do not Bushnell.
OK, so if the front element is not null, then what will do?
So I will print, I will print and now I will check, so I will check.
If left exist, then push left inside the queue and if right to exist, then push right inside the queue.
OK, so I will follow these steps.
I will follow these steps.
Now let us first let us create given Bush two things, OK.
So CU is basically built in big data subject and C++, OK, so I have to create a queue of three a.m.
OK, not often tedious.
I have to create new freenode style so that I can access the left and the right subtree.
OK, it will not be often tedious.
It will be of order because I have to access it left and right subtree.
OK.
So let's Namadgi only.
Then good old Bush, I have to push two things first one is the.
Second one is Denel character.
OK, now this special character.
That will help us differentiate between levels.
Now, again, what we have to do so while is not empty, got a different element.
So while she not empty.
What I have to do is get different element, OK, and friend element is basically adrenalized start.
So.
Dean, Alstyle, let's call it friend.
OK, so Dean or storefront is basically good old friend.
So I have the front element now I have to check, so I have to use this condition, I have to compare
different elements within a different element or not.
OK, so let's check.
So if a friend element is null.
I have to do something.
In the last part, I have to do something else.
OK, so now first let's write the l'esprit, OK, first let us write this part so I do not have to print
anything.
I have to basically store it, OK, I have to store it now.
Let's do it and I will check if left and right exist then push.
OK.
So basically, what is the data, so data is not value.
OK, so I was told it and temp Fambul Sturdee current level.
So Temperton push back.
What is the value, so value is basically f d'arte value.
OK.
So the FLW.
So if it's different element, I am pushing its value.
OK, now I have to check.
So if the left exist.
Then I have to push it inside the so called out push left.
Similarly, I will check.
So if right to exist.
Then I will push the right.
OK, very, very simple.
Now, let us do this part.
OK, so in this part, our first step was to basically do so out and line.
But here we do not have to print anything.
So instead of printing a new line, what we will do?
I will push my answer.
OK, so this is our answer.
What is temp?
So temp is basically storing the result of current level.
OK, temp is storing the result of current level.
Now, at this point, the current level has been finished, if I may, and counting.
Well, that means the current level has been finished.
So what I will do vs my answer so we don't.
Push back, so I have to push a vector and temp is that vector means temporary.
OK, so after pushing the temp, what I will do, I will make the temp empty.
OK, so I think that clearly is a function.
Our team members now empty, it does not contain a single element, it is containing zero elements.
What I'm not clear.
Now, I would have to do.
So you can see yourself, I have to see out and then I will check if the queue is not empty.
Bushnell again.
OK, so very simple condition.
So if.
The queue is not empty.
Then I have to push again.
OK, so not.
Bushnell.
OK, so I think.
After this line, basically, while.
The queue is becomes empty out until it's ready, and my answer is to be so let's sit in our court and
then we will try to submit our good.
OK, so what is the edit spelling mistake?
OK, so we are getting time limited exit.
That means there is some infinite loop, this is not becoming empty.
OK.
OK, so what we are doing so after getting a different element.
So first thing.
We are getting excited, so this is very simple, so we are getting excited because we are popping different
element and we we are getting different elements.
So this is to get a different element.
I have to also pop different elements, so I have to write good pop.
So basically, you will never become empty, OK?
You will never become empty and it will become infinite loop.
OK, so that's why because of the infinite loop, I am getting timely and excited.
So after getting different element, I have to also pop that element.
You can see yourself.
So basically, after getting a different element, I also have to pop their element, OK, and if I
got to pop here now, let's pop the element.
So could our friend then, good artpop, we also have to remove the element.
OK.
OK, so now let's meet our good.
OK, so if basically the tape does not exist, we do not handle that case, OK, so let's handle that
case.
So if the route isn't.
So if rotational.
Then what William Allen said.
So basically my answer will be empty.
OK, so return V V is empty at this point, OK?
V is not containing anything.
So I will return my.
OK, so our goal is 100 percent correct.
Our goal is working fine.
OK.
Now, let us discuss the time and the space complexity of our resolution.
So what is the time, complexity, so time, complexity is very simple, it is big often where and is
the number of nodes in the binary.
OK, we are just going through each and every node and we are outputting that node via printing that
node.
OK, so NQ basically every operation, this operation is basically Konstantine.
This operation is also constrained.
OK, so Bush operation is also constrained.
So NQ everything is Konstantine.
So basically our time complexities big off and only.
OK, and what is our space complexity.
So what we are doing, we are using accum we are creating a AQ.
So in the worst case our space complexity will be big often.
OK.
So this is the time and the space complexity, more time, big of an.
So these are the time and the space complexity for the level of the traversal.
OK, so if you have any doubt in the code or in the logic, you can ask me, OK, thank you.