Welcome back.
Now let's go ahead and code the solution which we discussed to get the right view and the left view
of the binary tree which is given to us.
Now over here we have the node class and the binary tree class and the insert function which we have
discussed previously.
So using this we have created this binary tree.
Now let's go ahead and write the function to get the right view first.
So let's just call it right view.
And this function is going to take in the root of the binary tree.
Now this is going to be very much similar to the function which you have written to get the level order
traversal of the given tree.
Because we are implementing this over here using the breadth first search approach.
So over here first we will check if the root is null.
So if the root is null then we will just return an empty array.
Now if this is not the case let's have an array which we will call right.
Let's just call it right.
So this is going to be an empty array.
And then finally we will just return this array.
So this is how we are going ahead.
And then we will need a queue.
As we've seen in the video where we discussed level order traversal, this is going to be a breadth
first search approach which we are implementing over here.
So we will need a queue.
And initially we will put the route into the queue.
All right.
Now we will just have a while loop.
And this will keep looping as long as something is there in our queue.
So we can say while queue dot length.
Now when the length is equal to zero this will become false and we will come out of the while loop because
zero in JavaScript is falsy.
All right, now inside this while loop, we are again going to have to compute the length of the queue
at that particular time.
So we say let length is equal to q dot length.
And then we'll have a count right.
So let count is equal to zero.
So this is similar to what we have seen in the level order traversal function.
And then we will have one more while loop over here.
And this will go on as long as count is less than length.
So while count less than length we will keep looping right.
And inside this let's increment count.
Now, if the count is equal to the length of the queue, then we know that we are at the last element,
right?
So then we will know we are at the last element.
And as we have discussed in the concept video previously, we just want the last element for the right
view at that particular level.
So let's just find the current element.
So let's say const current is equal to q dot shift.
Now, if the count is equal to the length, let's check that if count is equal to the length.
In that case, we know that we are getting the rightmost element in that particular level, and in that
case we have to do right dot push.
We have to push it to the output array.
Right.
So that particular value.
And again we just want the value.
So we will just say current dot value.
So we are pushing that particular value to the output array which is right.
We have just called it right over here.
Now we just proceed.
And we are checking if there is something to the left of the current node.
So if current dot left.
Then we will just NQ it.
So we'll say q dot push.
Current left.
And similarly we will check if there is something to the right, like so.
Let's check.
Let's just check that.
So if current dot right.
One minute.
I'll just have this over here.
Now over here.
We'll check if current dot.
Right.
Now.
If it is there, then we will push it to the q.
So q dot push current dot right.
So this is the same thing that we have seen whether in breadth first search or in the function where
we discussed level order traversal.
Now once we are just out of this right.
So once we are out of this while loop, we will have pushed only one element to the uh, output array,
which is right over here.
Right.
Which is this case.
If count is equal to length, then we will push that value to the array which we call in this case.
Right.
And then over here we just returning this view.
So let's go ahead and run this function and let's see if it is working.
So before that, I'll just draw this out so that we can visualize this in a better manner.
All right.
So I have just drawed drawn our binary tree over here.
So this is how it looks.
Now let's go ahead and call this function which is right view.
And let's pass the route to it.
So we have right view and tree dot route.
So that's the route of this binary tree.
And then let's just run it and take a look at the output.
So we are looking at the right view.
Right.
So we are looking at the binary tree from the right.
So over here we will see seven.
So we have seven over here.
And then in this level we will not see 11.
We can only see one right.
So yes that's also correct.
So when we look at this.
Way right from the right we are seeing, we can only see one.
So that's why we have one over here.
And then in this level we can only see eight, seven and two are blocked by this node.
So we have eight over here.
And then we can see three and we can see five.
So yes our function is working.
Now let's also go ahead and write the function to get the left view of the tree.
So that's going to be a minor modification.
So let's take a look at that now.
So let's go ahead and write that function.
So for this I will just make a copy of this.
And let me just paste it over here and we will say left view.
So we will call this function left view.
And this function is again going to take in the root of the tree.
And then let's call this.
Left.
So because this is the left view and then we will return left view right.
So let's just return left.
All right.
Now we do this again.
We will put the route into the queue.
And then as long as something is there in the queue, we will loop through.
So this is the same.
We find the length, we find the count and while count is less than length, now we are inside this.
Now in each level.
Initially count is zero, right?
So when we come inside we increment count.
So count will become one.
Now if count is equal to one, we know that we are looking at the leftmost element in that particular
level.
Right.
And again it is one because we have incremented at this point itself.
If I take this and put it at the end, then it would be zero.
So we are over here.
We just have to make a check if count is equal to one.
In that case we are going to push to left right the particular value.
So left dot push current dot value.
And then we are just checking if there is something in the left.
Then we push it to the queue.
If there is something in the right we push it to the queue and that's it.
Right.
And then we are going to return left.
So this should give us the left view of this particular binary tree.
So let's go ahead and call the function.
So let me just comment this out and then we will call the left view function.
And let's pass tree dot root over here.
And let's take a look at our output.
All right.
So we are getting 711 735.
Now we are looking at the binary tree over here from the left which is from here.
So we will see seven.
So we have seven.
And then in this level we will only see 11 right.
So we have 11.
And one cannot be seen because 11 will hide it.
And then in this level we will only see seven.
So we have that over here.
And then we will see three and five.
And we have these two also here.
So yes this function is also working.
And this gives us the left view of this binary tree.
Now let's take a quick look at the space and time complexity of our solution.
So let me just clear this up.
All right, now, let's just, uh, get this a bit down.
So we have our functions over here to find the left and right view.
Now, how many times will this how many operations will happen over here?
Now you can see we are actually doing the same number of operations as we are doing in the case of level
order traversal.
So over here, this function over here, this while loop over here will actually make n operations where
n is the number of elements in the binary tree.
Right.
Because we are going to loop through every element once because we are traversing.
Right.
So that's why over here we'll have n operations.
And this will have operations which is equal to the number of levels.
So that's why.
Because n will be greater than number of levels, we can say that the time complexity of this solution
will be of the order of n, and that's the same case for the left view as well.
And when it comes to the space complexity, we can see that the complexity is also O of n.
Why is that so?
Because first of all we have the queue, right?
And we are.
If you are looking at the worst case possibility again, if you have a full binary tree, the last level,
right, the number of leaves can be equal to n by two.
And then we can say that the space complexity is o of n by two.
And because this is just a constant, we remove it and we get that the space complexity is O of n.
But when it comes to the output array right or the right or left side view, that is not going to take
n space, that's going to take less space, right?
It's going to take the uh, the number of levels it will be.
It will have the, uh, space equivalent to the number of levels.
So we can say this will take space of the order of number of levels, because that is the number of
elements that will be there in our output array.
But because we are doing a Big-O analysis over here, we always take the worst case possibility.
And that's why we can say that the space complexity also is O of N, because in the worst case, the
queue will take O of n space.