Welcome back.
In this video, let's discuss how we can implement the level order traversal function.
So let's say this is the binary tree which is given to us.
And if we do a level order traversal of this binary tree the output should be this one over here.
Right.
Every level is made one array.
So we have seven.
Over here we have 11 comma one which is this level.
And then we have 728 which is this.
And then we have three.
And then we have just five.
So this is the level order traversal.
So we are going level by level.
And the elements in each level is made one array.
And that's pushed to our output array.
So this should be our output array.
Now before we go ahead and discuss how we can write this or how we can make this an algorithm, how
we can write this function, let's do a few observations.
The first observation is if we just do breadth first search on this binary tree, what is it that we
would be getting right?
In that case we would get this array 711 1728, three and five.
So you can see that it's the same order.
The elements are in the same order right now.
The only difference is that we have to split every level into an array.
So for example this is one array 11 and one is a one array.
Over here 728 is one array and three and five are separate arrays.
So we just need to modify our breadth first search algorithm to have a mechanism whereby which we can
make each level a separate array.
So this is the first observation.
All right.
Now let's proceed.
Now again let's say we start at the root node.
So this is the root node.
Now let's have our breadth first search algorithm over here.
So there we just have a while loop right.
While something is there in the queue.
Initially we add the root node into our queue.
And then while something is there in our queue we dequeue from the queue.
We push to our output array if that is required.
And then we enqueue the left and right.
So this is how our typical breadth first search works.
Right now let's think how we can modify this a little bit to make the output like this which is our
level order traversal.
Now for this to get some intuition before we start to go ahead and write the function and the solution.
To get some intuition, let's just trace the queue during this process.
All right.
So we have our queue over here.
Now initially we have our root node in our queue.
Now, once we are inside this right, we will dequeue this.
But I'm not removing it.
I'm just keeping it there.
We will dequeue this.
All right.
And then we will push the left and right of this queue this particular node into our queue.
So in this case that's 11 and one which will happen over here.
Right.
We will enqueue the left and right of the current node which is 11 and one.
And later when we take out 11 we will push its children right, which is seven at this point.
And then when we dequeue one we will push its children, which is two and eight, into our queue.
So this is how our queue proceeds right now.
If we just can have a count variable, let's say we have a count variable and let's say we have a while
loop.
Such something like while count is less than q dot length.
In that case this.
We could use this to club the elements of a level together, right?
For example, initially the queue just has one element and then the count is zero.
Initially, let's say we have the count equal to zero initially, and the queue length is one at that
point.
So we will just have one element right.
So while zero less than one.
Yes that's true.
So we get one element.
And then let's say we increment the count.
So we say count plus plus and count becomes one.
Right.
So we can just separate this out together.
And which is what we want as per the output that we want right now.
Let's say we are done with this.
And we know that by this time we have enqueued these two elements.
So the queue has these two elements, right.
So the length at that point is going to be equal to two.
And again count is zero right.
So you can see that we can use this mechanism to get these two together.
We get these two clubbed together right.
Now what?
After this?
Like, let's say we are done with processing these two elements.
So when we process this, we will be enqueuing seven and when we process this we will be Enqueuing two
and eight.
So once we are done with this right, once we are done with this, once we are out of this while loop,
when count is equal to two, then at that point, right, what would be the length of the queue?
The queue?
The length of the queue at that point would be three, right.
Because these three elements will be there in our queue.
And yes, we can see it's these three elements that we want together.
So this is the intuition that we have developed over here when we trace how the queue functions.
Right.
So we can see that if we just take the length of the queue and then if we have a count variable which
is initially zero, and then we go up to the length of the queue, right.
So using this we can club the elements at a particular level together.
So this is how we are going to go ahead and solve this question.
So let's try to implement this intuition into our function.
So again over here we have our output array which is what we have to develop.
And we start at the root node.
And we have our while loop over here.
And then we have our queue.
Now this while loop is going to loop as long as there is something in the queue and initially, like
in a typical breadth first search algorithm, we insert the root node into our queue.
Now we calculate that the length is one, right, the length is one, and the count at this point is
initialized to zero.
And we will also need a variable.
Let's call it car level which will be an empty array.
And we are going to insert the values in the current level into this empty array.
And then we will push this array to our output array.
So this is how we are going to proceed.
Now initially count is equal to zero.
And the length of the queue at this point is equal to one.
Now we are going to have the while loop which we discussed and while count less than length, we are
going to do the operations that we typically do in a breadth first search operation, which is dequeue,
push and enqueue the left and right elements.
All right, the notes.
The only difference over here is that we are not going to push to the output array, but rather we are
going to push to car level.
Right.
This this variable over here, which is an empty array at this point.
And then once we are out of this while loop, we will push car level to our output array.
So this is how we will proceed.
And then remember we need to loop as long as count is less than length.
So after we are done with one pass we have to increment count over here.
So we say count plus plus.
All right.
Now again and again as we discussed after we are out of this while loop, we will push car level to
our output array.
So this is the pseudocode of our algorithm.
Now let's trace it.
Initially the count is zero.
Length is one.
So yes zero is less than one.
So we come inside and we dequeue.
So we take out seven and we push it to our car level.
So let's just have car level over here.
Now this is going to be an array with just the element seven.
And then we enqueue the left and right.
So the left and right is 11 and one right.
So we are going to enqueue 11 and one at these steps.
And then we increment count.
So count becomes equal to one.
Now again we come and check over.
Here is one less than one.
No that's falsy.
So we come out and at this line of code right at this place we are going to push car level which is
just an array with one element seven.
We are just going to push it to our output array.
So we get this over here.
All right.
Now again we are going to come over here.
Car level is going to be an empty array.
And at this point uh again we will need to initialize or change our count to zero because at this point
count became one.
Right.
So we make again the count equal to zero.
And car level is an empty array.
And the length the length over here is equal to two.
Right.
So we have to compute the length.
The length of the queue at this point is equal to two.
So let's change that and write two over here.
So the length is two.
Now zero is less than two.
So we come inside the while loop we dequeue.
That is we take out the 11 and we push it to our car level which just has 11 at this point.
And we enqueue the left and right of 11, which is only seven.
We don't enqueue the null.
So we enqueue the seven over here.
And then we are incrementing the count.
So the count becomes one.
All right.
So the count becomes one.
And then again we dequeue we dequeue.
So the count is one.
We'd queue and we took one.
And we push it to our car level.
So we get one over here and we enqueue the left and right.
So the left is two and the right is eight.
So two and eight get enqueued over here.
And then we increment the count.
So the count becomes two.
Now two less than two is falsy.
So we come out and we are going to push this car level into our output array.
So we get 11 comma one which is an array over here to our output array.
All right let's proceed again.
We change count to zero.
And the length of the queue at this point is equal to three.
So we change this to three.
So we have the length three.
The count is zero.
And car level is again an empty array now zero less than three.
So we come inside we dequeue and then we push it to our car level.
And again we come over here.
We check its left and right.
We don't have anything to enqueue at this point right.
Because its left and right are null.
Over here again we increment count.
So count becomes one.
One is less than three.
Again we come inside VDC two.
We push it to car level and its children three this is null.
So null does not get enqueued.
But three over here gets enqueued.
All right.
And we increment count.
So count is equal to two.
Two is less than three.
So again we come inside VDC.
That is we take the eight and we push it to car level and its left and right which is null.
So we don't have anything to enqueue at this point.
And count is again incremented to three.
Now three less than three is falsy.
So we come out of the while loop this one over here and we are going to push car level to our output
array, which is this array over here with three elements seven, two and eight.
All right.
Now again we come and we are we are again over here right.
So again count is changed to zero.
And the length at this point is equal to one.
The length of the queue is equal to one.
So we change that and then car level is.
Again, an empty array.
Now zero less than one, which is truthy.
So we come inside, we dequeue.
So we take the three and we push it to our care level.
And its children, which is five only.
Right.
It just has one child five.
So that gets enqueued and count is incremented to one.
Now one less than one is falsy.
So we come out and we push this this care level three into our output array.
Again we come over here count is changed to zero.
Right count is changed to zero.
And the length at this point is again one.
So it's one only now we we see that zero less than one is true.
Three we come inside VDC this five and we push it to our car level and then its children.
It does not have any children, nothing to NQ.
And then we increment count.
So one and then one less than one is false.
So we come over here and at this point we push this to our output array which is the array with just
one element five.
So this is how this function works.
And this is how we get our output array which is the level order traversal.
So every level is made into one element.
So we have seven.
Then we have 11 17283.
And then we have five.
So this is how this algorithm works.
Now let's discuss the complexity analysis of this solution which we just now discussed.
The time complexity of this solution is going to be of the order of n, where n is the number of elements
in our binary tree.
Why is that?
So we are visiting every node one time right.
So you can see that we are visiting every node one time.
So that is happening over here.
Right?
This while loop over here will execute n number of times where n is the number of nodes in our binary
tree.
Right.
Because we are going to dequeue and we are going to push into car level.
And you can see that every value over here in the binary tree is there in some element or the other
over here.
So that's why this will operate n number of times.
Right.
For one time for every element in our binary tree.
So we are doing n operations over here.
And then we have a while loop over here.
Right.
You can see we have this while loop over here.
This while loop is going to do number of operations which is equal to the number of levels.
Right.
Because this takes care that the elements in one level are clubbed together.
So it will do 123455 operations for this binary tree over here because it has five levels.
Right.
So this is going to do operations equal to the number of levels.
But because we can be sure that n is greater than the number of levels, we can just say that the time
complexity is of the order of n.
Or we can say it's of the order of n plus number of levels.
But again, because n is greater than number of levels, we can just ignore this because this will dominate.
And that's why we can say that the time complexity is of the order of n.
Now what about the space complexity?
For this.
Let's think about what are the things in our algorithm that takes up space, that can scale when the
input scales, right when the input n increases.
So we have our queue which we are using.
And then we have our output array.
Now the output array is going to have every element right.
Every element has to be there in our output array.
So that's why we can clearly see that the output array is going to take space of the order of n.
So this is going to be o of n space.
Now what about the queue for this.
Again because this is a big O analysis.
Let's think about the worst case of the queue.
Now when will this happen?
If we are having a full binary tree in the last level we have previously seen, there will be elements
of the order of n by two, right?
For example, over here you can see we have 15 elements.
So this is eight.
So exactly this eight would be equal to n plus one by two.
Right.
So that's approximately n by two right.
So approximately n by two elements.
Or we have eight elements over here.
Or again we are seeing off the order of n by two elements.
Again.
I'm just writing it over here.
Exactly.
We can say it's n plus one by two elements, but then these are just constants, right?
So that's why I can say it's of the order of n by two elements.
So we can say that the space complexity of the queue in the worst case will be of the order of n by
two.
Why is that so.
Because you can see when we are processing this level, right, we are going to dequeue this particular
node and we will enqueue these two.
Then we will dequeue this one.
We will enqueue these two.
We will dequeue this one.
We will enqueue these two.
We will dequeue this one and we will enqueue these two.
So at that instance all these eight nodes are going to be there in our queue.
Right.
So that's why we can say the worst case space complexity of the queue is going to be of the order of
n by two.
And because this is just a constant, this one by two.
Right.
We can just avoid that.
Right.
So we can just avoid that.
And that's why we can say that the space complexity is also of the order of n.
So the time complexity is of the order of n.
And the space complexity of a solution is of the order of n.