Hi, everyone.
So in this video, we are going to solve this question, Zig-Zag level, order traversal.
OK, so this is simply a variation of Lavallette, but now let's see what is the question?
So basically, this is the binary.
So what will be the Zig-Zag?
So this will read this order, then this line and then this line.
OK, so what will be our output?
So I will be three, then I have twenty, then nine, then fifteen and then seven.
OK, so we are traversing in the exact manner.
Now let us try to find out these exact level or traversal for this by Nutri.
OK.
So.
First this order, then Zig-Zag.
Then this level and then this level.
And then finally, this last level.
OK, so what will be our output?
So I have 50, then I have 21, seven, so 21 and seven, then I have eight, 10 and nine.
Then I have seven.
Twenty one and one.
So this is seven, then 21, then one.
And then I have 15.
OK.
So this is this is exactly reversal for this by Nutri.
OK, so I hope you understood the question.
OK, so this question is very similar to Louella traversal, but now I have to change the order.
OK, so first I am traversing in this order, then I am traversing this order, then I'm traversing
this order, then this and this.
OK, so in the exact manner we are traversing that tree, we are processing the train level orders,
exact manner.
OK, so let's see how we can solve this question.
So it is simply a modification of lavalier traversal.
So we will modify our level order drivers a logic a little bit.
OK, so let's take a small example.
OK, so basically let us take a small example.
So suppose this is the boundary.
OK, so suppose this is the boundary.
Now what do we lose?
Our logic is very simple.
We are taking a cue.
OK, very simple.
We are taking a cue.
Just like the simple level rhetoric was initially, our goal will be empty.
Initially, our crew is basically empty.
OK, so what we will do again, logic, simple logic pushed the root element, OK, nothing new, nothing
new here.
OK, so this is my output, basically.
So till now, we have nothing new, simple, all the cold.
OK, now again, so since first I'm going from left to right, then I'm going from right to left, then
I'm going from left to right, then right to left.
OK, so to change this order, let let's take a variable left to right.
OK, so initially this values through.
So what I'm telling you is let's take a variable left to right.
OK, so this is a boolean variable.
So for this initially, this boolean variable will be true.
So Left-to-right is initially true.
OK, so for this line, the for this level, Left-to-right will be true, for this order, for this
level, basically left to right will be false.
So false means.
But I was from right to left, OK, for this line, either left to right will be true.
And for this level either left or right will be false.
OK, so if the left left-to-right right is basically false, if it is false, that means Trivers from
right to left.
If it is true, that means drivers from left to right.
OK, very simple.
We have to take this variable.
It is mandatory OK, because I have to change how we are trellising.
OK, so this is minor.
This variable is mandatory.
OK, so initially I can say initially my left-to-right is basically true.
OK, for first level, OK, now what we will do so again, simple could pop different element and bend.
So I am popping different elements and I will print.
OK, so in the question, if you will see, I do not have to print, I have to write an integer.
So basically what I will do.
I will pop different elements before popping different element, what I will do, I will find the size
of the cube.
So what is the size?
Size is one.
Size is one, so basically what I will do since the sizes one.
I will first create a vector of size one.
OK, I will first create havoc both sides, then I will check, left-to-right, destroy.
OK Bob the element and put it at the first index three.
Very simple.
After writing three here.
What I will do, I will check.
So left exist.
Right exist.
Push left and right.
So it will be nine and twenty and I will also change the order.
OK, so I will make it false.
I will make it false.
OK now again so check.
So Bob different element nine.
So before popping out different element.
First find out the size.
So size of the cube is basically two societies two.
So I will store two elements.
OK, and now the value of Left-to-right is basically false.
OK, so basically this is different elements so I will start it here.
This is the second element Bob twenty also and I will store it here.
OK, so when you the nine you will check left and right does not exist then you probably 20 left exist.
Yes.
Right exist.
Yes.
So push 15 and seven.
Bush fifteen and seven.
OK, so now let's see again, so again, what do will do, I will change its value values through again.
OK, now what will do so pop different element before popping out of entitlement can criticize society
is basically to say this too.
So again, creative process too.
It will store two elements.
OK, so it is left to right is true.
So first element will be here.
Second element will be here.
OK, so 15 is the first element.
So put 15 here.
Check left exist.
Three is right exist.
Yes.
Push 89, push eight and nine.
OK then pop the element seven and started here.
OK, so then again what we will do so after popping all seven left and right does not exist.
OK, now I will change its value to false.
Now let us again find out the size.
So size is basically two sizes, too.
So make a vector of size to.
OK, so first, children will be stored here.
Second element will be stored here.
So it is the first element storyteller here now check left and right does not exist, so nine is the
second element.
So store nine here, left and right, 11 does not exist, so do not push anything.
Finally, our goal will become embittered and we will stop.
And this is my answer.
OK, this is my answer.
Which is correct.
I have three, then I have 29, then I have 15 and seven, and then I have nine indeed.
OK, let us take one more example for better clarity.
Now, this time, let us take a bigger example.
OK?
OK, so now our logic is very simple.
Makoko.
Let's take seven here and let's take eight and nine here.
OK?
So, again, this is Michael Semple with 20.
So this is grunty.
Here, I will write my output.
Left to right variable is initially Drew.
OK, now let's see Top-up different element.
So before popping out, different color decides the size is basically one, size is one.
Make of it better off, says one.
OK.
Right.
Don't be here now, Jack, left, exist, right, exist, push them.
So this is 17 and this is 15.
OK, now for the next level, change the value so its values now falls.
Now we'll find out the size, so size of the queue is basically two sizes, too, so make of it.
But again, size to first element will come here to come here.
OK, so seven is the first element.
Seven will come here now check.
So left of seven exists.
It is seven only so push seven.
Right of seven exists it is eight.
So push it now.
This is the second element.
So push 15.
OK, very, very simple.
Now, again, it will become true.
OK, so we'll find out the size.
So size is basically two, OK?
So for 15, I forgot 20 exist, left, existing right exist.
So Bush turned down 15.
I am pushing 20 and 15.
OK, now find out the size.
So it size is basically four sizes four.
So create a vector of space for.
OK, the first element, the second element, third element in fourth element.
Now, seven is the first element, so that I had seven here check left exist, yes, right exists to
push them eight and nine.
Now, this is the second element.
So this is eight left exist.
No right exist.
No push.
The third the third element.
Now, Jack, so grunty recently, yes, so left exist.
OK, so basically this was an audit, this was it.
OK, so left exist.
No right exist.
No.
OK, now I have 20 Sawchuk left exists.
Right exists.
So Bush 15 and 16.
Now, Bob, 15.
Right, 15 here, no left exist, no right exist.
Yes, this is 22, right, 22 here.
OK, now, again, change its value to false.
Now find the size, so size is basically five.
So this is basically, if you can see at this level, the number of nodes are five, so that's why the
size is five one, two, three, four and five sizes five.
I am calculating size and then I am making the vector of that size.
OK.
So at this level, the number of nodes was four, so my size was four at this, nor the number of levels
the number of nodes was to.
So my size of the vector was to add this level.
The number of nodes was one, so the size was one.
OK, now at this level the number of nodes are five.
So that's why you can see the number of nodes are five, the size of the is five.
So that's why I have to create a vector of size five.
OK, so first element will come here, second element will come here.
Third element will come here for Telemed will come here, fifth element will come here because the value
is false.
OK, so Bush got it so right here, here.
OK, so this is it, left and right does not exist.
So do nothing now pop nine so right nine here, left and right does not exist.
Do nothing.
Now, about 15, right, 15 here, so left exist, right exist 18 and 19, so 18 and 19.
Now, pop, 16, right, 16 here, so left and right does not exist, pop 22, right, 22 here.
So left and right does not exist.
Do nothing.
OK, so now find out the size.
So first I will make it through, now find out the size of the council size.
The sized is basically the face of the accused, basically to say, I will make a vector of size two.
First element will come.
Our second element will come here because the value is true.
OK, you can see at this note to notice at present.
So let's say size, vector size will be two.
OK, so palpating right in here left exist.
Right does not exist to push five.
So push five.
Now, Prop 19, right, 19 here, left and right, doesn't exist to do nothing.
OK, now again, find out the size of the queue.
Before we will make it false.
OK, so the size of the queue is basically five, so make a vector.
So OK, so size is basically one, so make a vector of size one.
It will store only one element.
Element five.
So Bob Delamare, five, left and right, does not exist or do nothing.
Finally, I would Google become embittered and we will stop gambling and we'll stop.
And this is my answer.
OK, this is my answer, you can see 20.
Then I have 15 and seven and then I have seven, eight 2015, then I have 22, 16, 15, nine, and
then I have 18 and 19 and then I have five.
OK, very simple.
Understood.
Now let us write the code.
OK, so the code is going to be very, very simple.
This will be very similar to the level traversal.
OK.
Now, let us write the code again so we have to return to profitability, just so, let us create our
answer.
So the prospect of integers, let's name it, we you can name it, result also.
OK, so let's name it result.
This will store our result.
OK, now the best case.
So if basically route is null.
That ministry is empty, so, my --, I will also be empty so I can return here.
OK, now again, I was code.
We will make you.
Now, this time, you will again be of North Star, because I have to check for left and right.
OK, so Guilfoile, North Star, let's name it.
Q So to start the full loop, I have to push the Rudimental to push Bushrod Standard called.
Now, I told you I have to take a variable left.
Right.
So bool.
Left to right.
OK, so initially this will be through.
I will constantly change its value.
OK.
So this is the variable bull left-to-right.
I will constantly change its value.
Now what we have to do, so our standard condition value is not empty.
I have to do some work.
OK, so what is the work that I have to do?
So if we can see carefully, first of all, I am calculating the size.
I am calculating the size of the queue and then I am preparing my vector.
OK.
So find the size and make a vector of that size.
Make a vector of that size.
OK.
So first, let us find out the size of the.
How many elements are present at this point inside the cube?
OK, so this is good size.
So what it will return me, so basically it will return me at this level, how many nodes are present?
OK, so the size so good our size means how many nodes are present at this level.
OK.
So this is the meaning of size, how many roles are present at this level?
OK, now I will create a vector of that size so that part of integers, let's name Mitro, OK, because
Romy's so basically this is the first rule.
This is the second, OK, and this is the third rule, so let's name it so you can name it anything.
OK, I have to create a vector.
Of this size.
OK, so this size is basically the sunglasses, OK?
You can see.
So this is phase one, that process to, again, victory phase two.
OK.
So after creating director directorate, I have to do so basically I have to pop I have to pop size
element, so let us pop the element.
So I have to publicize elements, OK, I have to publicize elements.
Now, what we are doing so at this point, what we are doing, we are traversing the current level.
Traversing current level, OK, we are traversing the current level because in the current level, how
many nodes are present size and all that present?
So I am traversing FaceTime, so that means I am traversing the current level.
OK, I am traversing the current level to.
Let us pop out different element, so Renauld Star F is basically good old friend.
OK, and good artpop, otherwise we will get family mutex.
OK, good.
Pop is necessary.
Now I have to decide.
OK, so at this point what I have to do, so I have to decide whether I have to fill this out in this
way or I have to fill the vacuum in this way.
OK, I have to decide.
So how we can decide.
We can decide with the help of this left-to-right.
OK, so basically this is SKU.
OK, these are some elements.
So first element, this has two choices.
Either it will come at this point, basically at this starting point or it will come at the ending point.
OK, either the first element will come at this starting point, if left to right is basically true,
if left right is basically false, it will come at the last weekend.
OK, so let's find out the index of the first element.
Let us find out its index.
So its index will be zero or its index will be basically Saiz minus one.
OK, size minus one means this one.
The last index.
OK.
So let us find out the correct position for the settlement, so, OK, so basically let us use the operator.
OK, so Left-to-right.
So if left to right is basically so I'm using the radio operator.
So if Left-to-right is true.
Then Texas A.
If we have to right this falls, then its index is basically says minus one, minus a.
OK, and then what they will do after finding out the correct.
Next, let's push the current element at its right index.
OK, so this is ephemeral value.
Very simple.
And then if left exist, Bush left, if right exist, Bush right.
This is standard code.
OK, so if left exist, so culotte Bush left.
Similarly, airfreighted exist.
Then Guillard Bushrod.
OK, so what I'm doing here is so I told you, I suppose this is the cue, OK, this is the cue and.
So the first element of the Q so this first element can come here or the first element come can come
here if they're left to prove a loose fault, if we have to prove is true, then it will come here.
Otherwise it will come here.
OK, so basically this is to the.
This the radio operator.
So if it is true, then this line will be executed.
If this is false, then this line will be executed.
OK, I'm repeating myself.
So intracerebral know what happens.
So if this condition is true, if it is true, then I will execute this line.
And if this is false, if this is false, I will execute this line after this column.
OK, after this column, I will execute this line.
So what I am doing, I am trying to find out the right index for the current element.
OK, so after finding out the right index, I am pushing the limit.
So this is the element.
I am pushing the element to it.
Right index.
OK, and then this is standard.
If left exist, push left or right exist.
Both right.
OK.
So after traversing the current level.
OK, so the current level has been finished.
OK, so current level has been finished.
So basically now let us reach the next level.
So after the current level.
So after the current level traversal is done, what I have to do, I have to change the value of Left-to-right,
I have to make it false.
If it was true, I have to make it true.
If it was false.
OK, so Left-to-right is basically equal to.
Rivers of Left-to-right.
OK, so after the current level of the current level has been reversed and its output has been stored,
but I have to do I have to change the value.
So if Left-to-right was true, it will become false.
OK, OK, so if the left right was true, it will become false.
If the left-to-right was false, it will become true.
OK.
So I'm changing the value of left to right now after changing the value of Left-to-right.
Let us push the current level inside our research director, so deserted Dot.
Push back.
What is my answer so ruys, my answer.
OK.
You can see it clearly, so this is it.
I am pushing all inside this one, OK, so it is at least containing my answer.
So it is Eldard push becquerel, OK, because this level has been finished.
So after traversing the current level, let us push the current level into our answer.
And finally, when the will become embittered and will break, I can return desert.
OK, so this is the complete code now, alerts are now called.
OK, so now let's meet.
OK, so our goal is hundred percent correct.
Now, let us take a very small example and let us read another code.
OK, so let us take very small example.
So I have three, then let's in nine the example given indication, OK, 15 and seven on.
I'm taking a very small example.
OK, so cute.
Or Bushrod and Left-to-right value is true.
OK, so basically this is the dequeue.
It is containing only one element, which is tree, OK, and this value, so left to right value is
basically true at this point is not empty.
Find out the size.
So size is basically one size is basically one.
Make a vector of size one.
So I am making a vector of size one.
So this is a vector of size one.
OK, now I lost the current level so size the value size is one.
So but I was the current level which is three only.
OK, it is containing only one element which is three.
So get different elements of different elements of pop the element.
Now find out the index, so left right values basically true, so the value of five will be zero and
basically the index will be zero.
OK, the index is zero rule of Index 040.
So this is the rule of zero.
It is containing the value three.
OK, now check left exist.
Yes, nine exist to push nine.
Now, right, exist, yes, it is 20, so push 20.
OK, and now the current level has been finished.
OK, so this was the current level, the current level has been finished.
I am changing the value of Left-to-right so it will become false.
And I am pushing the arrow in the result that, OK, so this is the result of a bigger one.
So this has been pushed.
OK, so this small role has been pushed, Zimbelman.
Now, again, the queue is not empty.
It is containing Element 1920.
Now let us find out the site.
So this team decides is to OK, nine and 28 is containing the element.
So the site is basically two.
You can see at this level, two nodes are present.
OK, so now let us reverse the current level.
So in the current level, 1920, they are two nodes.
OK, so four I called you.
I left inside the various sizes, basically two.
So I will loop will run two times.
OK does get different elements.
So this is different.
Nine nine is different.
OK, so one thing, I have created a vector of size two so this is my vector of size to.
OK now Bob the front element this is nine.
Now, let's find this index.
OK, so left-to-right value is basically false.
So this is false.
This will be my index.
So says the value of is to soar to minus one.
The value of is zero.
OK, so this is basically one.
So I will push nine here.
Bush nine here now check Jack, left and right of nine exist, no, it does not exist, so do nothing.
OK, now what will happen this little pestilential times?
So let us run this loop one more time now, Bob.
Twenty, find the index of 20, so find the index.
So this is basically sizes two minus one.
The value of A is one.
OK, so it's index zero.
So I have to push that index zero.
I have to push Rohloff index value.
So low of zero is value.
I lose 20, so I will push 20 here.
OK, and then left exist, right exist, so yes, 15 and seven exists to push them.
So I have 15 and seven, OK, Bush 15 and seven then, but I will do so after traversing the current
level.
Current level has been finished.
After trouncing the current level.
I am changing the value of Left-to-right so it will become true again and I'm pushing my role in that.
OK, so this is the situation of my electorate as containing three then it is containing twenty nine.
OK, now, again, what we will do so find out the sides, find out the sides, you can see I am finding
out the size and then create a vector of that size.
So find out the size and create a vector of that size.
So I will create a process to then pop different element, which is 15, find the right index with the
help of this.
Left right values, basically true, so the index is basically zero.
So I will push 15 here left and right of 15 does not exist.
So do nothing then Bob.
The next element seven right index is basically the value of AI is basically one.
So put seven here, then left and right does not exist.
So left and right does not exist.
Then what I will do so change the value of left right.
So it will become false again, then push this inside the vector so it will become fifteen and seven.
And then what I'm doing here is so if you will go up, the queue is now empty.
OK, who is now empty?
And then I am returning my.
So this is my result.
This is my desert and I will return this result.
OK, so this is the complete logic and the complete Driton.
OK, so what is the time and the space complexities of time?
Complexity is just big.
Often we are going through each and every now and again.
The space complexity is also big.
Often we are using you OK.
So this is basically the complete.
OK, now this is a new technique, this technique will be used many times.
OK, so traversing the current level.
So how are you going to basically find out the size, make a vector of that size and reverse the current
level?
OK, so this is a new technique that we have not seen before.
OK, traversing the levels.
OK, we are traversing the compute levels three dendrobium.
We are introducing nine and 20, then I'm turning 15 and seven.
OK, so this is new technique, finding out the size and then reversing the current level.
OK, so if you have any doubt in this question you can ask me.
Thank you.