Welcome back.
Now to solve this question, let's see how we can make slight modifications to the algorithm of the
level order traversal to get our answer.
So first over here let's try to think about right side view.
All right.
So you're looking from the right.
So you should be getting 7183 and five.
And this is the algorithm which we discussed.
Or the pseudocode which we discussed when we had the video on level order traversal.
All right.
So over here what we want is again let me let's just quickly recap.
We start at the root node.
Now we're going to insert it to our queue.
All right.
And then we will find the length of the queue which is equal to one at this point.
And then the count is initialized to zero.
And then there is something in the queue.
So we come inside this while loop.
Now there in level order traversal, we needed an array to have all the elements in that particular
level, right.
So that's why we had car level which was an empty array.
But over here we don't need this.
So I'm just removing this now.
We still need this over here.
Right.
For again in this part we said count is equal to zero and we find the length.
So we have found the length is equal to one.
Now we have this while loop which will operate while count is less than length.
Now inside this while loop we dequeue so that the the process is the same we dequeue.
Then over here we have this step where we push to current level.
So we don't need this over here.
Right.
So we don't need this because we are not discussing level order traversal.
We are going to enqueue the left and right.
And then we will increment count.
So this is going to be the same.
Now after we increment the count we can check whether we are at the right most element of the particular
level.
So how can we check that.
Right.
For example, if let's say over here, we are over here.
Right.
So initially count is equal to zero.
Now length is one.
Now when count is equal to zero we come inside and we increment count.
So count becomes one.
So when count is equal to length right.
Then if if we make that check over here then we can be sure that we are at the right most element in
that particular level.
Right.
So if count is equal to length we just need to push it to our right array.
So let's call this array right view.
All right.
So we just need to push it the element to our right view array if the count is equal to the length.
So in this case we push seven because the count is equal to length because after we increment count.
All right.
So after we increment count inside this itself we can check or we can write it outside also.
So I'm just going to check it inside.
So if count after incrementing.
All right.
So it's going to be somewhere over here.
If count is equal to the length then we are just going to push it to our array over here.
So in this case we push seven.
Now we proceed again we have enqueued our left and right over here.
So 11 and one are going to be in our queue.
And again this this thing over here is not required.
Again we are not dealing with level right.
So I'm just taking this over here so that you can work upon something which you have already seen so
that you can build upon the knowledge.
Right.
So again, we come over here, we see that there are things in our queue.
So we come inside.
Count is equal to zero.
And length at this point is made to two.
Because we have two elements in our queue.
Now we come inside and zero is less than two.
So we come inside VDC and we are going to enqueue its children, which is just seven, and we will increment
count.
So count is equal to one at this point.
And again these two are not equal.
So again we come over here we dequeue.
So we take one out and we enqueue its children which is two and eight.
Again, we increment count.
So count becomes equal to two at this point.
Now count is equal to length.
So this particular element right which we just now took out which is one is going to be pushed into
our right view.
So we get one over here and then we proceed.
We see that again there are things in the queue.
All right.
So we again change count to zero.
And length now is equal to three.
So length is equal to three.
Again we come inside zero is less than three.
So we dequeue and we are going to enqueue its children.
So there are no children.
And then we will increment count.
So count is equal to one.
Again we'd Q all right.
And we're going to enqueue its children which is three.
So we add three over here.
And count now is equal to is incremented.
So count becomes two.
Two is also not equal to length.
So again we come over here and we dequeue right.
So we dequeue we take this eight.
Now count becomes three.
When we again it does not have any children to enqueue.
And then we increment count.
So now count is equal.
So because count is equal to the length we will just push that particular value which is eight to our
output array.
So you can see we are getting 718 right.
Similarly we continue again we see that there is one element in our queue.
So we come inside.
Count is again changed to zero.
So let's just clear this up.
So count is again changed to zero.
And length now is equal to one.
So we come inside VDC this and it has children.
It has five.
So we enqueue the child and then we increment count.
So one.
Now count is equal to length.
So this element, the element which we just now dequeued is going to be added to our right view array.
So we get three also.
And then we again come over here we see that there are things in the queue we dequeue right.
So again over here the length was set to one.
Count is now zero.
We come inside this VDC this and we it does not have any children.
We increment count and now count is equal to length.
So this also is going to be added to our right view.
And this gives our answer which is 7183 and five.
So this is the answer for our right view.
Now let's also quickly discuss how we can build the left view with the same logic.
So it's going to be pretty much similar.
And I'm sure you must have solved it on your own.
But just for completeness sake, let's discuss the left view also over here.
Again, we are starting with the algorithm which we had previously.
So I'm just removing current level from here.
And I'm removing removing current level from here as well.
And this also all right.
And we have our left you array over here.
So this is going to be the same.
Only the check is going to be different.
So inside this after enqueuing we are going to check if count is equal to one.
So initially count is zero for every level right.
So when we are inside and when we increment count once then for the first element count will always
become one right.
So if count is equal to one then we will just push it to our left array.
So let's try.
So initially we add seven to our queue.
And then we come inside because there is something in our queue.
Count is zero and length of the queue is one.
Now we come inside over here because zero is less than one.
We dequeue this seven and we are going to enqueue its children which is 11 and one.
All right.
And then over here again this push also I'm removing over here we are going to increment count.
Count becomes one.
Now we are checking whether count is equal to one.
Yes.
Count is equal to one.
Therefore we are going to push this to our left view.
So we get seven over here.
And again we continue right.
So we come over here we see that there are elements in the queue.
So we come inside.
Count is again changed to zero and the length of the queue is equal to two.
And we proceed right.
So again zero is less than two.
So we come inside.
We dequeue this one.
All right.
So 11 is dequeued and we enqueue its left and right.
So only one child is there.
So seven is enqueued and then count is incremented.
So count becomes one.
We are checking if count is equal to one.
Yes count is equal to one.
So this gets added to our left view array.
So we push it to our left view array.
Again we come over here we see there are things in in our um queue.
Right.
So we are over here in this part.
The count is just one at this point.
All right.
So we come over here one is less than two.
So again we come inside.
We dequeue this.
But at this point again one has children two and eight.
So let's enqueue the children and then current becomes two.
Right.
So the count becomes two.
So two is not equal to one.
So we don't push this.
All right.
So at this point when we come over here two less than two that's falsy.
And we come to this while loop.
So this is how it proceeds.
Now we have these three elements.
Now let's proceed.
Let's just clean this up a little bit.
All right.
So at this point again count is changed to zero.
The length over here is equal to three.
And then we come inside.
So zero is less than three.
We come inside VDC this and we are enqueueing its children.
It does not have any children.
Then we increment count to one and we check count is equal to one.
So yes, we are taking this.
So we put it over here.
All right.
We push it to our left view array.
Again we are going to do this.
We come over here and one is less than three.
So we take out two and we enqueue its children which is just three at this point.
And we increment count.
So two and count is not one right.
So we are not pushing to our left array and we get two less than three when we check this while loop
condition.
So we again come inside over here and we are going to dequeue.
So we take this and we enqueue its children.
So it does not have any children.
Now we are checking whether and again we increment count.
So count becomes three.
We are checking if three is equal to one.
No that's not true.
So we come again over here now three.
Less than three.
That's falsy.
So we come to this while loop.
Again we have one element in our queue.
So we come inside.
And the length at this point is equal to one.
So let's just clean this up.
The length that this point is equal to one the count is again changed to zero now zero less than one.
So we come inside VDC and its children.
We add its children which is just five.
And then we are incrementing count.
So count becomes one.
So yes one is equal to one.
That's true.
So we push.
So this value over here is pushed to our left view.
Now we we again come over here.
One less than one is falsy right.
So we come out of this while loop.
We come over here and we check if there is something in the queue.
Yes, we have this element in the queue again we come inside so count is changed to zero and length
again is one and zero less than one.
So we come inside VDC this element which is five.
And its children.
So there are no children to NQ and we increment count to one.
Now we see that count is equal to one.
Therefore we are pushing this value also to our left view.
And we get we when we come over here one less than one.
So that's falsy again.
When we come over here there is nothing in our queue and we come out of the function call and this is
our left view.
Seven and then we have 11, then we have seven, then three and five.
So this is the left view array.
So you can see that both the right view and left view is very much similar to the level order traversal
which we discussed.
Now what about the time and space complexity of these solutions.
The time complexity is going to be O of N because we are visiting every node one time.
Right.
So it's it's just breadth first search.
So the time complexity is straightforward O of n.
What about the space complexity.
Now what are the things that take up space.
We have the queue that takes up space.
And we also have the array the output array right the left or right view.
So this also takes up space.
Now the queue can go up to size n by two.
Right.
Because we have seen that in the case of a full binary tree there can be n by two leaves.
So that's why we can say that the queue takes space of the order of n by two.
But when it comes to the output array, it's going to take space of the order of the number of levels.
Right.
So for every level either the leftmost if it's the left view or the rightmost if it's the right view
will be there in the output arrays.
So the number of elements is going to be less than n in the case of this left or right view right.
So we don't need to consider this because this is going to be less than n.
But when it comes to the queue it's going to have n by two elements.
So the space complexity of this is going to be o of n by two.
And because two is a constant, we can just avoid this.
And we can say that the space complexity of this solution is of the order of n.
So the time complexity is O of n and the space complexity is O of n.