Welcome back.
Let's now go ahead and write the level order traversal function that we just now discussed.
So over here I have our node class.
Then I have our binary tree class.
And we have already discussed the insert function which we have written together.
So this array has been passed to it.
And we have already created our binary tree.
Now we will go ahead and write the function which will take in the root of this tree.
And we will traverse this tree level order.
So let's go ahead and write this function and let's call it level order traversal.
All right.
Now this function is going to take in the root of the tree.
All right.
Now, once you're inside this function, we will just check if the root is null.
So if not root, then we will just return an empty array.
Now, if this is not the case, we proceed.
So let's have a variable.
Let's call it output.
So this is going to be an empty array.
And we will traverse this tree which is given to us.
And we will fill in the arrays, the levels.
Right.
One level will be one array.
We will fill those arrays to this output array.
And finally we will just return this output array.
So this is how we will proceed.
And we also need q a q.
Right.
So let's say const q.
And initially we will fill the root into this array.
Now over here we are implementing the Q as an array.
But ideally to get a optimum time complexity when you are taking out L because we will be taking out
elements from the beginning of the queue.
So you have to use a linked list to implement this queue, because in JavaScript there is no inbuilt
queue data structure, but over here it's fine.
Typically in an interview to save time we will use an array when we implement a queue.
But be sure that you mention this to your interviewer and mostly they will be okay, because that's
not the central question over here.
The central question is level order traversal.
So let's proceed.
Now we have inserted the root to the queue and then we will have a while loop.
And this will loop as long as something is there in the queue.
So while queue dot length.
So this is what we have seen in the case of breadth first search the same thing.
So while queue dot length.
And then we will have our loop over here.
Now again as we discussed in the previous video, we will make some changes over here.
Now initially once we are inside this loop let's identify the length of the queue at this point.
So let length is equal to q dot length.
And then we will have a counter.
So let's say let count is equal to zero.
Now we will have one more while loop over here.
And this will go on looping as long as count is less than length.
Now it is here that we will develop or build each current level value, which will be an array.
And once we are out of this while loop, we will push it to the output array which we created over here.
All right.
So once we are inside this while loop let's shift the first or dequeue the first element from the queue.
So we can say const cur which is the current element is equal to q dot shift.
So we take out the first element from the queue and then we will push it to the current level.
All right.
So for this we will need the current level.
So again let's create that over here.
So initially let let's say current level at this point is an empty array.
So const.
Car.
Let's just call it car level.
Values or.
Yeah values.
So that is an empty array.
All right.
So again whenever we come back over here it will be a new level.
Right.
So again we make it empty at this point.
So once we are inside this while loop we will just push this curve to the current level values.
So we can say for level values.
Dot push.
And then, as per the question, we only want the value of the node, right?
So we can say cur dot value at this point.
So we are pushing the value of the current node to the uh cur level value array.
Now what we will do is we will check if there is something to the left of the current node and if it
is there, we will push it to the queue.
And again we will do the same thing for the right.
So this is what we have seen always in breadth first search.
So the same thing is what we're doing over here.
Now let's continue.
So if.
Current.
Dot left.
So if there is a node to the left of the current node, again this is curved, so curved or left.
So if curved or left then we will push it to the queue.
So we say queue dot push.
Car dot left.
And we do the same thing for.
Right.
So if car dot right.
We push it to the q so q dot push.
Car dot.
Right.
All right.
And then we just have to increment the count so we can say count plus plus.
So this will go on looping as long as count is less than length and it will come out when count is equal
to length, right?
So at that point we will just push to the output array.
So we say output dot push.
The core level values.
And this will be an array.
So this array is pushed into the output array.
And that's it.
And once we are out of this while loop we will have gone through every level.
And then we have to just return the output.
So let's go ahead and test this.
So we have our binary tree over here.
Let's just quickly draw it out together.
And then we will see whether when we call the level order traversal function whether we are getting
the correct output.
So let's just check that out.
All right.
So I have drawn the binary tree over here.
Now let's call the function.
So level order traversal.
And we will be passing the root of this binary tree to this function.
So we say tree dot root we pass tree dot root.
All right, so let's run our code.
And let's take a look at the output.
So we are getting an array of arrays.
So that's correct.
So let's take a look.
So the first element is seven which is this one over here.
And then we have 11 comma one which is this level.
Then we have 728 which is this level.
And then we have three.
And then we have five.
So yes our function is working.
Now let's try to walk through the code and see what's happening.
So here is our function.
And this is the binary tree which we have.
Now let's say the root which is seven is past and we are inside this function.
So let's take a look at the code and walk through what's happening over here.
Now first we come over here right.
So when we are over here we see that the root is not null.
So we come over here and output at this point is empty is an empty array.
So let's just have output over here.
This is an empty array.
And then we come over here we have the queue.
So let's just have the queue also over here.
And at this point we put the route into the queue.
So we have seven inside the queue.
Then we come over here, we see that there is something in the queue, right.
So we come over here and the length we identify the length is equal to one.
Now we make count as zero initially.
And then we have car level values which is an empty array.
All right.
So we go we are going to this while loop.
And this will loop as long as count is less than length.
So count is zero.
Zero is less than one.
So we come inside.
We shift from the queue.
So we get seven right.
So this node is taken out and then we push it to car level values.
The value of this particular node which is seven.
So we get seven over here.
And then its left is n cubed which is 11.
So we put 11 over here.
And then its right which is one that is also n cubed.
We get one also over here and we increment count.
So count becomes one and now one less than one.
This is false.
So we come out of this while loop.
And then at this line we are going to push car level values which is this array over here into the output
array.
So we get seven over here.
All right.
So once that is done, we again come over here and we come inside the while loop because we have two
elements inside the queue.
So the queue is not empty.
So again the length is now calculated which is two at this point.
So this is equal to two.
And count is changed to zero.
So count is zero.
And then car level values is an empty array at this point again.
And then zero is less than two.
So we come inside.
We shift.
So we take 11 out and we push it to the car level values array.
Over here the value 11 is pushed over here.
And then it's left and right.
So it's left is null.
So uh that is this is false.
So we don't push uh null to the uh, queue.
But when we come over here this is truthy.
Right.
So there is a node over here.
So seven is pushed to the queue.
So we get seven over here and count is incremented.
So count becomes one.
So again one is less than two.
So we come again inside.
We shift.
So we take one out.
And we put that to car level values.
Over here we push it to car level values.
And then it's left and right which is two and eight.
Get enqueued so we get two and eight over here and count is incremented.
Now two is not less than two.
So we come out of this and this over here this array 11 comma one is pushed to the output array.
So we get 11 and one over here 11 comma one over here.
All right.
Now let me just clear this up a bit.
So in our queue we have seven, two, eight.
And again we come over here.
Length is now calculated.
It's equal to three right.
So let me just clear this up.
So length is equal to three.
And the count is again initialized to zero.
And car level values is empty is an empty array at this point.
Now zero less than three.
So we come inside VDC.
We take out seven and we push it to the car level values array over here.
And then it's left and right which is null right.
So these two are null.
So nothing gets n cubed over here.
And count is incremented at this point.
Again one is less than three.
So VDC and we push it to car level value.
So we get two over here and then it's left and right.
So it's left is null.
It's right is three.
So three gets added over here.
And then car the count is incremented.
So we have two.
Two is two is less than three.
So again eight is dequeued.
And we push it to the car level values array over here.
And at this point count will be incremented to three.
Now three is not less than three.
So we come out and this over here is pushed to our output array.
So we get 728 over here.
All right, so that's how we got to that place.
So let's just get this back and just going to make some space over here.
Now in our queue we just have three right.
So again when we come over here the queue is not empty.
Right.
So we come inside.
Now the queues length is one.
The count is again initialized to zero.
And kernel level values again is an empty array at this point right over here.
And we are now going to come inside the loop because zero is less than one.
Now we're going to shift.
So we take out three.
We put it to car level values.
We push it to car level values.
And then it's left and right.
So it's left is five.
So five gets enqueued.
So we get five over here into our queue.
Right.
And over here it's null.
So we don't have anything over here.
And then count is incremented to one.
One less than one is falsy.
So we come out and this over here is pushed to our output array.
So we get this element which is an array with only three into our output array.
And then finally again we have one element in our queue.
So again we come inside and we're queue length is at this point one right length is one count is changed
to zero when we come over here.
And then car level values is an empty array.
We dequeue when we come we we shift or we dequeue and then we push it to our car level value.
So we get five over here and count is incremented to one.
One less than one is falsy.
So at this point we are going to push this to our output array.
So this is also pushed to our output array.
And this is how our function works.
So this is how we do the level order traversal of the given binary tree.
Now let's take a look at the complexity analysis of this solution.
Now before this let me just clear up some space.
So let's just remove this part over here.
And, uh, let's just remove this also.
All right.
So again over here we had five.
And that that's coming over here in the output array.
Now let's take a look at the time complexity.
The time complexity of this solution is of the order of n, where n is the number of elements in the
binary tree.
Right.
So why is that.
So let's take a look.
What are the things that take up time.
So we have this while loop.
And then we have this while loop over here.
Now this while loop will operate as for once it will loop once for every level.
Right.
So this will be operating doing number of operations equal to the number of levels.
And in this case that's one, two, three, four and five.
Now what about this this while loop over here.
This while loop will loop for a number of times which is equal to n.
Right.
Because why is that so?
Because we have to create this this right.
For we have to create this output array.
And you can see that in each when you add these levels, every element over here 1234567, eight that's
equal to n which is equal to the number of elements in the binary tree.
So that is why it will keep operating for that.
Right.
Because we can see that every element at some point or other will come into our queue.
Right.
It will come into our queue over here.
And then we uh, we are incrementing the count and then we can see this is operating as long as count
is less than length.
So for example, in, in this level, right.
In this level it will happen once because the length is one so zero less than one.
So it will happen once.
So in this level you will have length as two so zero and one.
So this will operate two times.
Similarly over here it will operate for each of these elements.
So you can see that this over here this while loop will operate n number of times.
Now we can see that the time complexity is number of levels plus n.
But then this will be definitely be less than n right.
So that's why we can say that the time complexity of this solution is O of n.
Now what about the space complexity?
For this, let's think about the things that take up space that can scale when the input scales.
So we have our output array and then we have our queue over here.
Now in the output array we can see that we have all elements which are there in the binary tree.
So that's why we can say that the output array takes space of the order of n, where n is the number
of nodes or number of nodes in our binary tree.
Now what about the queue?
Now in the case of a full binary tree, right.
Something like this.
We know that.
The number of leaf nodes, right?
For example, over here you can see you have eight leaf nodes.
So this will be of the order of n by two.
Right.
So I'm saying of the order of n by two because exactly it will be n plus one by two.
But then we can say this will be approximately n by two.
If n is the total number of nodes in the binary tree.
All right.
Now all of these nodes will be there in our queue at the same time.
Right.
So all of these would be put into our queue at the same time when we are processing this level.
Right.
So when we when we dequeue this we will add these two elements.
When we dequeue this one we will add these two.
And these two are still there.
When we dequeue this we will add these two.
And when we dequeue this node we will add these two.
Right.
So all of these nodes are going to be there in our queue at the same time.
So that's why we can say that the queue will take space of the order of n by two.
In the case of a full binary tree.
And then this is just a constant.
So we can just avoid this.
So this also takes space of the order of n.
So again we can say that the space complexity is of the order of n plus n or two n.
But but then two is a constant.
So we can say the space complexity is nothing but O of n.