1 00:00:00,660 --> 00:00:01,740 Welcome back. 2 00:00:01,740 --> 00:00:07,710 Now let's go ahead and code the solution which we discussed to get the right view and the left view 3 00:00:07,710 --> 00:00:10,080 of the binary tree which is given to us. 4 00:00:10,110 --> 00:00:15,810 Now over here we have the node class and the binary tree class and the insert function which we have 5 00:00:15,810 --> 00:00:16,830 discussed previously. 6 00:00:16,830 --> 00:00:19,620 So using this we have created this binary tree. 7 00:00:19,650 --> 00:00:23,460 Now let's go ahead and write the function to get the right view first. 8 00:00:23,460 --> 00:00:25,410 So let's just call it right view. 9 00:00:26,990 --> 00:00:30,860 And this function is going to take in the root of the binary tree. 10 00:00:30,890 --> 00:00:36,020 Now this is going to be very much similar to the function which you have written to get the level order 11 00:00:36,020 --> 00:00:37,400 traversal of the given tree. 12 00:00:37,400 --> 00:00:41,300 Because we are implementing this over here using the breadth first search approach. 13 00:00:41,300 --> 00:00:44,090 So over here first we will check if the root is null. 14 00:00:44,720 --> 00:00:48,290 So if the root is null then we will just return an empty array. 15 00:00:48,560 --> 00:00:53,630 Now if this is not the case let's have an array which we will call right. 16 00:00:53,630 --> 00:00:55,040 Let's just call it right. 17 00:00:55,040 --> 00:00:56,540 So this is going to be an empty array. 18 00:00:56,540 --> 00:00:58,670 And then finally we will just return this array. 19 00:00:59,850 --> 00:01:01,560 So this is how we are going ahead. 20 00:01:01,560 --> 00:01:03,360 And then we will need a queue. 21 00:01:03,360 --> 00:01:08,970 As we've seen in the video where we discussed level order traversal, this is going to be a breadth 22 00:01:08,970 --> 00:01:11,340 first search approach which we are implementing over here. 23 00:01:11,340 --> 00:01:13,050 So we will need a queue. 24 00:01:13,050 --> 00:01:15,840 And initially we will put the route into the queue. 25 00:01:15,870 --> 00:01:16,680 All right. 26 00:01:17,340 --> 00:01:19,380 Now we will just have a while loop. 27 00:01:19,380 --> 00:01:23,130 And this will keep looping as long as something is there in our queue. 28 00:01:23,130 --> 00:01:25,290 So we can say while queue dot length. 29 00:01:25,920 --> 00:01:30,690 Now when the length is equal to zero this will become false and we will come out of the while loop because 30 00:01:30,690 --> 00:01:32,280 zero in JavaScript is falsy. 31 00:01:32,670 --> 00:01:38,220 All right, now inside this while loop, we are again going to have to compute the length of the queue 32 00:01:38,220 --> 00:01:39,540 at that particular time. 33 00:01:39,540 --> 00:01:44,070 So we say let length is equal to q dot length. 34 00:01:46,220 --> 00:01:47,810 And then we'll have a count right. 35 00:01:47,810 --> 00:01:49,460 So let count is equal to zero. 36 00:01:49,460 --> 00:01:53,600 So this is similar to what we have seen in the level order traversal function. 37 00:01:53,600 --> 00:01:56,420 And then we will have one more while loop over here. 38 00:01:56,720 --> 00:02:00,440 And this will go on as long as count is less than length. 39 00:02:00,440 --> 00:02:04,460 So while count less than length we will keep looping right. 40 00:02:04,460 --> 00:02:07,340 And inside this let's increment count. 41 00:02:08,670 --> 00:02:15,030 Now, if the count is equal to the length of the queue, then we know that we are at the last element, 42 00:02:15,030 --> 00:02:15,300 right? 43 00:02:15,300 --> 00:02:17,460 So then we will know we are at the last element. 44 00:02:17,460 --> 00:02:23,400 And as we have discussed in the concept video previously, we just want the last element for the right 45 00:02:23,400 --> 00:02:24,930 view at that particular level. 46 00:02:24,930 --> 00:02:27,360 So let's just find the current element. 47 00:02:27,360 --> 00:02:31,770 So let's say const current is equal to q dot shift. 48 00:02:35,040 --> 00:02:41,670 Now, if the count is equal to the length, let's check that if count is equal to the length. 49 00:02:41,670 --> 00:02:47,910 In that case, we know that we are getting the rightmost element in that particular level, and in that 50 00:02:47,910 --> 00:02:49,800 case we have to do right dot push. 51 00:02:49,800 --> 00:02:51,330 We have to push it to the output array. 52 00:02:51,330 --> 00:02:51,810 Right. 53 00:02:51,810 --> 00:02:53,040 So that particular value. 54 00:02:53,160 --> 00:02:54,780 And again we just want the value. 55 00:02:54,780 --> 00:02:56,430 So we will just say current dot value. 56 00:02:56,430 --> 00:03:00,810 So we are pushing that particular value to the output array which is right. 57 00:03:00,810 --> 00:03:02,790 We have just called it right over here. 58 00:03:02,790 --> 00:03:04,140 Now we just proceed. 59 00:03:04,140 --> 00:03:07,440 And we are checking if there is something to the left of the current node. 60 00:03:07,440 --> 00:03:09,000 So if current dot left. 61 00:03:10,110 --> 00:03:11,610 Then we will just NQ it. 62 00:03:11,610 --> 00:03:13,170 So we'll say q dot push. 63 00:03:14,530 --> 00:03:15,640 Current left. 64 00:03:16,970 --> 00:03:20,180 And similarly we will check if there is something to the right, like so. 65 00:03:20,180 --> 00:03:20,570 Let's check. 66 00:03:20,570 --> 00:03:21,470 Let's just check that. 67 00:03:21,470 --> 00:03:23,600 So if current dot right. 68 00:03:25,650 --> 00:03:26,130 One minute. 69 00:03:26,130 --> 00:03:27,930 I'll just have this over here. 70 00:03:27,930 --> 00:03:28,680 Now over here. 71 00:03:28,680 --> 00:03:29,670 We'll check if current dot. 72 00:03:29,670 --> 00:03:30,300 Right. 73 00:03:32,200 --> 00:03:32,620 Now. 74 00:03:32,620 --> 00:03:34,300 If it is there, then we will push it to the q. 75 00:03:34,300 --> 00:03:36,910 So q dot push current dot right. 76 00:03:37,510 --> 00:03:41,500 So this is the same thing that we have seen whether in breadth first search or in the function where 77 00:03:41,500 --> 00:03:43,450 we discussed level order traversal. 78 00:03:43,510 --> 00:03:46,480 Now once we are just out of this right. 79 00:03:46,480 --> 00:03:52,120 So once we are out of this while loop, we will have pushed only one element to the uh, output array, 80 00:03:52,120 --> 00:03:52,990 which is right over here. 81 00:03:52,990 --> 00:03:53,260 Right. 82 00:03:53,260 --> 00:03:54,250 Which is this case. 83 00:03:54,250 --> 00:03:59,590 If count is equal to length, then we will push that value to the array which we call in this case. 84 00:03:59,590 --> 00:03:59,980 Right. 85 00:03:59,980 --> 00:04:02,020 And then over here we just returning this view. 86 00:04:02,020 --> 00:04:05,860 So let's go ahead and run this function and let's see if it is working. 87 00:04:06,530 --> 00:04:11,150 So before that, I'll just draw this out so that we can visualize this in a better manner. 88 00:04:11,810 --> 00:04:12,170 All right. 89 00:04:12,170 --> 00:04:15,710 So I have just drawed drawn our binary tree over here. 90 00:04:15,710 --> 00:04:16,850 So this is how it looks. 91 00:04:16,850 --> 00:04:20,870 Now let's go ahead and call this function which is right view. 92 00:04:20,870 --> 00:04:23,060 And let's pass the route to it. 93 00:04:23,690 --> 00:04:26,660 So we have right view and tree dot route. 94 00:04:26,660 --> 00:04:29,060 So that's the route of this binary tree. 95 00:04:29,710 --> 00:04:33,340 And then let's just run it and take a look at the output. 96 00:04:33,340 --> 00:04:35,050 So we are looking at the right view. 97 00:04:35,050 --> 00:04:35,230 Right. 98 00:04:35,230 --> 00:04:38,710 So we are looking at the binary tree from the right. 99 00:04:38,710 --> 00:04:40,180 So over here we will see seven. 100 00:04:40,180 --> 00:04:41,470 So we have seven over here. 101 00:04:41,470 --> 00:04:44,200 And then in this level we will not see 11. 102 00:04:44,200 --> 00:04:45,460 We can only see one right. 103 00:04:45,460 --> 00:04:47,470 So yes that's also correct. 104 00:04:47,470 --> 00:04:49,030 So when we look at this. 105 00:04:49,800 --> 00:04:52,620 Way right from the right we are seeing, we can only see one. 106 00:04:52,620 --> 00:04:54,180 So that's why we have one over here. 107 00:04:54,180 --> 00:04:58,380 And then in this level we can only see eight, seven and two are blocked by this node. 108 00:04:58,380 --> 00:04:59,520 So we have eight over here. 109 00:04:59,520 --> 00:05:02,400 And then we can see three and we can see five. 110 00:05:02,400 --> 00:05:04,650 So yes our function is working. 111 00:05:04,650 --> 00:05:11,100 Now let's also go ahead and write the function to get the left view of the tree. 112 00:05:11,100 --> 00:05:13,290 So that's going to be a minor modification. 113 00:05:13,290 --> 00:05:15,690 So let's take a look at that now. 114 00:05:16,410 --> 00:05:18,480 So let's go ahead and write that function. 115 00:05:18,480 --> 00:05:20,940 So for this I will just make a copy of this. 116 00:05:22,710 --> 00:05:26,790 And let me just paste it over here and we will say left view. 117 00:05:26,790 --> 00:05:28,950 So we will call this function left view. 118 00:05:30,470 --> 00:05:33,620 And this function is again going to take in the root of the tree. 119 00:05:33,620 --> 00:05:35,630 And then let's call this. 120 00:05:36,510 --> 00:05:37,560 Left. 121 00:05:37,560 --> 00:05:40,980 So because this is the left view and then we will return left view right. 122 00:05:40,980 --> 00:05:42,720 So let's just return left. 123 00:05:43,790 --> 00:05:44,330 All right. 124 00:05:44,330 --> 00:05:46,940 Now we do this again. 125 00:05:46,940 --> 00:05:48,800 We will put the route into the queue. 126 00:05:48,800 --> 00:05:52,070 And then as long as something is there in the queue, we will loop through. 127 00:05:52,070 --> 00:05:53,240 So this is the same. 128 00:05:53,240 --> 00:05:58,580 We find the length, we find the count and while count is less than length, now we are inside this. 129 00:05:58,580 --> 00:06:00,590 Now in each level. 130 00:06:00,590 --> 00:06:02,180 Initially count is zero, right? 131 00:06:02,180 --> 00:06:04,700 So when we come inside we increment count. 132 00:06:04,700 --> 00:06:05,990 So count will become one. 133 00:06:05,990 --> 00:06:11,780 Now if count is equal to one, we know that we are looking at the leftmost element in that particular 134 00:06:11,780 --> 00:06:12,050 level. 135 00:06:12,050 --> 00:06:12,350 Right. 136 00:06:12,350 --> 00:06:15,530 And again it is one because we have incremented at this point itself. 137 00:06:15,530 --> 00:06:18,590 If I take this and put it at the end, then it would be zero. 138 00:06:18,590 --> 00:06:19,790 So we are over here. 139 00:06:19,790 --> 00:06:23,120 We just have to make a check if count is equal to one. 140 00:06:23,480 --> 00:06:28,010 In that case we are going to push to left right the particular value. 141 00:06:28,010 --> 00:06:31,670 So left dot push current dot value. 142 00:06:31,670 --> 00:06:33,920 And then we are just checking if there is something in the left. 143 00:06:33,920 --> 00:06:35,240 Then we push it to the queue. 144 00:06:35,270 --> 00:06:37,730 If there is something in the right we push it to the queue and that's it. 145 00:06:37,730 --> 00:06:38,060 Right. 146 00:06:38,060 --> 00:06:39,590 And then we are going to return left. 147 00:06:39,590 --> 00:06:43,100 So this should give us the left view of this particular binary tree. 148 00:06:43,100 --> 00:06:45,050 So let's go ahead and call the function. 149 00:06:46,460 --> 00:06:51,140 So let me just comment this out and then we will call the left view function. 150 00:06:51,140 --> 00:06:53,900 And let's pass tree dot root over here. 151 00:06:54,290 --> 00:06:56,540 And let's take a look at our output. 152 00:06:58,840 --> 00:06:59,170 All right. 153 00:06:59,170 --> 00:07:01,600 So we are getting 711 735. 154 00:07:01,600 --> 00:07:07,090 Now we are looking at the binary tree over here from the left which is from here. 155 00:07:07,090 --> 00:07:08,230 So we will see seven. 156 00:07:08,230 --> 00:07:09,190 So we have seven. 157 00:07:09,190 --> 00:07:11,770 And then in this level we will only see 11 right. 158 00:07:11,770 --> 00:07:12,550 So we have 11. 159 00:07:12,550 --> 00:07:14,890 And one cannot be seen because 11 will hide it. 160 00:07:14,890 --> 00:07:17,170 And then in this level we will only see seven. 161 00:07:17,170 --> 00:07:18,430 So we have that over here. 162 00:07:18,430 --> 00:07:20,620 And then we will see three and five. 163 00:07:20,620 --> 00:07:22,270 And we have these two also here. 164 00:07:22,270 --> 00:07:24,370 So yes this function is also working. 165 00:07:24,370 --> 00:07:27,730 And this gives us the left view of this binary tree. 166 00:07:27,730 --> 00:07:31,780 Now let's take a quick look at the space and time complexity of our solution. 167 00:07:31,780 --> 00:07:33,520 So let me just clear this up. 168 00:07:36,880 --> 00:07:40,810 All right, now, let's just, uh, get this a bit down. 169 00:07:41,650 --> 00:07:45,670 So we have our functions over here to find the left and right view. 170 00:07:45,700 --> 00:07:49,150 Now, how many times will this how many operations will happen over here? 171 00:07:49,180 --> 00:07:54,430 Now you can see we are actually doing the same number of operations as we are doing in the case of level 172 00:07:54,430 --> 00:07:55,270 order traversal. 173 00:07:55,300 --> 00:08:02,050 So over here, this function over here, this while loop over here will actually make n operations where 174 00:08:02,050 --> 00:08:04,450 n is the number of elements in the binary tree. 175 00:08:04,450 --> 00:08:04,660 Right. 176 00:08:04,660 --> 00:08:08,500 Because we are going to loop through every element once because we are traversing. 177 00:08:08,500 --> 00:08:08,830 Right. 178 00:08:08,830 --> 00:08:12,070 So that's why over here we'll have n operations. 179 00:08:12,070 --> 00:08:15,610 And this will have operations which is equal to the number of levels. 180 00:08:16,240 --> 00:08:16,930 So that's why. 181 00:08:16,930 --> 00:08:21,250 Because n will be greater than number of levels, we can say that the time complexity of this solution 182 00:08:21,250 --> 00:08:26,290 will be of the order of n, and that's the same case for the left view as well. 183 00:08:26,290 --> 00:08:32,500 And when it comes to the space complexity, we can see that the complexity is also O of n. 184 00:08:32,500 --> 00:08:33,250 Why is that so? 185 00:08:33,250 --> 00:08:36,070 Because first of all we have the queue, right? 186 00:08:36,070 --> 00:08:36,640 And we are. 187 00:08:36,640 --> 00:08:43,540 If you are looking at the worst case possibility again, if you have a full binary tree, the last level, 188 00:08:43,540 --> 00:08:46,480 right, the number of leaves can be equal to n by two. 189 00:08:46,480 --> 00:08:49,720 And then we can say that the space complexity is o of n by two. 190 00:08:49,720 --> 00:08:55,030 And because this is just a constant, we remove it and we get that the space complexity is O of n. 191 00:08:55,030 --> 00:09:00,700 But when it comes to the output array right or the right or left side view, that is not going to take 192 00:09:00,700 --> 00:09:03,160 n space, that's going to take less space, right? 193 00:09:03,160 --> 00:09:07,270 It's going to take the uh, the number of levels it will be. 194 00:09:07,270 --> 00:09:10,990 It will have the, uh, space equivalent to the number of levels. 195 00:09:10,990 --> 00:09:16,780 So we can say this will take space of the order of number of levels, because that is the number of 196 00:09:16,780 --> 00:09:19,240 elements that will be there in our output array. 197 00:09:19,240 --> 00:09:24,460 But because we are doing a Big-O analysis over here, we always take the worst case possibility. 198 00:09:24,460 --> 00:09:29,950 And that's why we can say that the space complexity also is O of N, because in the worst case, the 199 00:09:29,950 --> 00:09:31,960 queue will take O of n space.