1 00:00:00,780 --> 00:00:01,470 Hi, everyone. 2 00:00:01,500 --> 00:00:06,870 So in this video, we are going to solve this question, Zig-Zag level, order traversal. 3 00:00:07,590 --> 00:00:12,540 OK, so this is simply a variation of Lavallette, but now let's see what is the question? 4 00:00:12,810 --> 00:00:14,520 So basically, this is the binary. 5 00:00:14,820 --> 00:00:16,140 So what will be the Zig-Zag? 6 00:00:16,350 --> 00:00:21,210 So this will read this order, then this line and then this line. 7 00:00:21,240 --> 00:00:23,060 OK, so what will be our output? 8 00:00:23,070 --> 00:00:29,230 So I will be three, then I have twenty, then nine, then fifteen and then seven. 9 00:00:29,280 --> 00:00:31,680 OK, so we are traversing in the exact manner. 10 00:00:32,220 --> 00:00:36,280 Now let us try to find out these exact level or traversal for this by Nutri. 11 00:00:36,340 --> 00:00:36,660 OK. 12 00:00:37,740 --> 00:00:38,190 So. 13 00:00:39,610 --> 00:00:42,970 First this order, then Zig-Zag. 14 00:00:44,140 --> 00:00:47,740 Then this level and then this level. 15 00:00:50,340 --> 00:00:52,940 And then finally, this last level. 16 00:00:53,160 --> 00:00:55,450 OK, so what will be our output? 17 00:00:56,070 --> 00:01:05,069 So I have 50, then I have 21, seven, so 21 and seven, then I have eight, 10 and nine. 18 00:01:05,519 --> 00:01:06,570 Then I have seven. 19 00:01:06,570 --> 00:01:07,490 Twenty one and one. 20 00:01:07,890 --> 00:01:11,550 So this is seven, then 21, then one. 21 00:01:11,940 --> 00:01:13,320 And then I have 15. 22 00:01:13,560 --> 00:01:13,980 OK. 23 00:01:15,050 --> 00:01:18,990 So this is this is exactly reversal for this by Nutri. 24 00:01:19,330 --> 00:01:21,500 OK, so I hope you understood the question. 25 00:01:21,620 --> 00:01:27,770 OK, so this question is very similar to Louella traversal, but now I have to change the order. 26 00:01:27,800 --> 00:01:33,620 OK, so first I am traversing in this order, then I am traversing this order, then I'm traversing 27 00:01:33,620 --> 00:01:35,550 this order, then this and this. 28 00:01:35,570 --> 00:01:40,900 OK, so in the exact manner we are traversing that tree, we are processing the train level orders, 29 00:01:40,910 --> 00:01:41,630 exact manner. 30 00:01:42,130 --> 00:01:45,750 OK, so let's see how we can solve this question. 31 00:01:46,190 --> 00:01:48,670 So it is simply a modification of lavalier traversal. 32 00:01:48,680 --> 00:01:52,460 So we will modify our level order drivers a logic a little bit. 33 00:01:52,490 --> 00:01:54,890 OK, so let's take a small example. 34 00:01:54,950 --> 00:01:58,340 OK, so basically let us take a small example. 35 00:01:58,700 --> 00:02:00,380 So suppose this is the boundary. 36 00:02:01,160 --> 00:02:02,810 OK, so suppose this is the boundary. 37 00:02:03,230 --> 00:02:04,400 Now what do we lose? 38 00:02:04,400 --> 00:02:05,600 Our logic is very simple. 39 00:02:05,630 --> 00:02:06,620 We are taking a cue. 40 00:02:06,690 --> 00:02:07,690 OK, very simple. 41 00:02:07,700 --> 00:02:08,780 We are taking a cue. 42 00:02:10,259 --> 00:02:13,860 Just like the simple level rhetoric was initially, our goal will be empty. 43 00:02:14,750 --> 00:02:16,670 Initially, our crew is basically empty. 44 00:02:16,710 --> 00:02:23,270 OK, so what we will do again, logic, simple logic pushed the root element, OK, nothing new, nothing 45 00:02:23,270 --> 00:02:23,670 new here. 46 00:02:23,690 --> 00:02:25,880 OK, so this is my output, basically. 47 00:02:26,860 --> 00:02:29,620 So till now, we have nothing new, simple, all the cold. 48 00:02:29,690 --> 00:02:36,760 OK, now again, so since first I'm going from left to right, then I'm going from right to left, then 49 00:02:36,760 --> 00:02:38,870 I'm going from left to right, then right to left. 50 00:02:38,890 --> 00:02:43,040 OK, so to change this order, let let's take a variable left to right. 51 00:02:43,090 --> 00:02:45,050 OK, so initially this values through. 52 00:02:45,550 --> 00:02:50,530 So what I'm telling you is let's take a variable left to right. 53 00:02:50,710 --> 00:02:52,600 OK, so this is a boolean variable. 54 00:02:53,540 --> 00:02:56,840 So for this initially, this boolean variable will be true. 55 00:02:56,990 --> 00:02:58,770 So Left-to-right is initially true. 56 00:02:59,050 --> 00:03:06,530 OK, so for this line, the for this level, Left-to-right will be true, for this order, for this 57 00:03:06,530 --> 00:03:09,130 level, basically left to right will be false. 58 00:03:09,470 --> 00:03:10,430 So false means. 59 00:03:10,580 --> 00:03:16,460 But I was from right to left, OK, for this line, either left to right will be true. 60 00:03:17,360 --> 00:03:21,380 And for this level either left or right will be false. 61 00:03:22,160 --> 00:03:27,500 OK, so if the left left-to-right right is basically false, if it is false, that means Trivers from 62 00:03:27,500 --> 00:03:28,270 right to left. 63 00:03:28,640 --> 00:03:31,340 If it is true, that means drivers from left to right. 64 00:03:31,370 --> 00:03:32,290 OK, very simple. 65 00:03:32,720 --> 00:03:34,010 We have to take this variable. 66 00:03:34,010 --> 00:03:38,480 It is mandatory OK, because I have to change how we are trellising. 67 00:03:38,490 --> 00:03:40,190 OK, so this is minor. 68 00:03:40,550 --> 00:03:42,200 This variable is mandatory. 69 00:03:42,900 --> 00:03:48,920 OK, so initially I can say initially my left-to-right is basically true. 70 00:03:49,950 --> 00:03:57,510 OK, for first level, OK, now what we will do so again, simple could pop different element and bend. 71 00:03:58,080 --> 00:04:00,840 So I am popping different elements and I will print. 72 00:04:01,490 --> 00:04:07,470 OK, so in the question, if you will see, I do not have to print, I have to write an integer. 73 00:04:07,650 --> 00:04:08,820 So basically what I will do. 74 00:04:09,840 --> 00:04:14,430 I will pop different elements before popping different element, what I will do, I will find the size 75 00:04:14,430 --> 00:04:14,830 of the cube. 76 00:04:15,240 --> 00:04:16,140 So what is the size? 77 00:04:16,140 --> 00:04:16,920 Size is one. 78 00:04:18,260 --> 00:04:22,010 Size is one, so basically what I will do since the sizes one. 79 00:04:23,040 --> 00:04:25,850 I will first create a vector of size one. 80 00:04:26,700 --> 00:04:31,920 OK, I will first create havoc both sides, then I will check, left-to-right, destroy. 81 00:04:31,980 --> 00:04:35,910 OK Bob the element and put it at the first index three. 82 00:04:36,720 --> 00:04:37,410 Very simple. 83 00:04:37,980 --> 00:04:39,330 After writing three here. 84 00:04:39,360 --> 00:04:40,440 What I will do, I will check. 85 00:04:40,770 --> 00:04:42,660 So left exist. 86 00:04:42,810 --> 00:04:43,530 Right exist. 87 00:04:43,530 --> 00:04:44,520 Push left and right. 88 00:04:44,520 --> 00:04:48,660 So it will be nine and twenty and I will also change the order. 89 00:04:48,700 --> 00:04:50,550 OK, so I will make it false. 90 00:04:50,790 --> 00:04:52,500 I will make it false. 91 00:04:52,800 --> 00:04:55,130 OK now again so check. 92 00:04:55,920 --> 00:04:57,950 So Bob different element nine. 93 00:04:58,230 --> 00:04:59,880 So before popping out different element. 94 00:04:59,880 --> 00:05:01,300 First find out the size. 95 00:05:01,300 --> 00:05:04,080 So size of the cube is basically two societies two. 96 00:05:04,080 --> 00:05:05,490 So I will store two elements. 97 00:05:06,310 --> 00:05:10,020 OK, and now the value of Left-to-right is basically false. 98 00:05:10,060 --> 00:05:13,220 OK, so basically this is different elements so I will start it here. 99 00:05:14,040 --> 00:05:17,640 This is the second element Bob twenty also and I will store it here. 100 00:05:18,570 --> 00:05:24,750 OK, so when you the nine you will check left and right does not exist then you probably 20 left exist. 101 00:05:24,750 --> 00:05:25,110 Yes. 102 00:05:25,110 --> 00:05:25,710 Right exist. 103 00:05:25,720 --> 00:05:26,000 Yes. 104 00:05:26,010 --> 00:05:27,600 So push 15 and seven. 105 00:05:28,380 --> 00:05:29,910 Bush fifteen and seven. 106 00:05:31,050 --> 00:05:37,860 OK, so now let's see again, so again, what do will do, I will change its value values through again. 107 00:05:38,410 --> 00:05:44,550 OK, now what will do so pop different element before popping out of entitlement can criticize society 108 00:05:44,550 --> 00:05:46,620 is basically to say this too. 109 00:05:46,650 --> 00:05:49,560 So again, creative process too. 110 00:05:49,560 --> 00:05:50,930 It will store two elements. 111 00:05:51,000 --> 00:05:52,980 OK, so it is left to right is true. 112 00:05:53,010 --> 00:05:54,210 So first element will be here. 113 00:05:54,210 --> 00:05:55,410 Second element will be here. 114 00:05:55,590 --> 00:05:58,100 OK, so 15 is the first element. 115 00:05:58,110 --> 00:05:59,300 So put 15 here. 116 00:05:59,700 --> 00:06:00,760 Check left exist. 117 00:06:00,760 --> 00:06:01,710 Three is right exist. 118 00:06:01,730 --> 00:06:02,020 Yes. 119 00:06:02,130 --> 00:06:04,390 Push 89, push eight and nine. 120 00:06:04,650 --> 00:06:07,910 OK then pop the element seven and started here. 121 00:06:08,890 --> 00:06:14,460 OK, so then again what we will do so after popping all seven left and right does not exist. 122 00:06:15,420 --> 00:06:17,760 OK, now I will change its value to false. 123 00:06:18,540 --> 00:06:20,540 Now let us again find out the size. 124 00:06:20,550 --> 00:06:22,830 So size is basically two sizes, too. 125 00:06:22,830 --> 00:06:24,600 So make a vector of size to. 126 00:06:25,690 --> 00:06:27,560 OK, so first, children will be stored here. 127 00:06:27,580 --> 00:06:29,040 Second element will be stored here. 128 00:06:30,290 --> 00:06:35,990 So it is the first element storyteller here now check left and right does not exist, so nine is the 129 00:06:35,990 --> 00:06:36,770 second element. 130 00:06:36,770 --> 00:06:41,390 So store nine here, left and right, 11 does not exist, so do not push anything. 131 00:06:41,570 --> 00:06:44,390 Finally, our goal will become embittered and we will stop. 132 00:06:45,110 --> 00:06:46,260 And this is my answer. 133 00:06:46,330 --> 00:06:48,260 OK, this is my answer. 134 00:06:48,950 --> 00:06:49,750 Which is correct. 135 00:06:51,120 --> 00:06:56,940 I have three, then I have 29, then I have 15 and seven, and then I have nine indeed. 136 00:06:57,510 --> 00:07:01,170 OK, let us take one more example for better clarity. 137 00:07:04,110 --> 00:07:06,200 Now, this time, let us take a bigger example. 138 00:07:06,240 --> 00:07:06,570 OK? 139 00:07:14,390 --> 00:07:17,210 OK, so now our logic is very simple. 140 00:07:18,280 --> 00:07:19,000 Makoko. 141 00:07:20,990 --> 00:07:25,880 Let's take seven here and let's take eight and nine here. 142 00:07:25,940 --> 00:07:26,290 OK? 143 00:07:29,320 --> 00:07:32,740 So, again, this is Michael Semple with 20. 144 00:07:34,330 --> 00:07:35,230 So this is grunty. 145 00:07:36,920 --> 00:07:38,390 Here, I will write my output. 146 00:07:39,590 --> 00:07:41,960 Left to right variable is initially Drew. 147 00:07:42,470 --> 00:07:45,600 OK, now let's see Top-up different element. 148 00:07:45,770 --> 00:07:50,690 So before popping out, different color decides the size is basically one, size is one. 149 00:07:51,680 --> 00:07:53,180 Make of it better off, says one. 150 00:07:54,330 --> 00:07:54,790 OK. 151 00:07:54,870 --> 00:07:55,240 Right. 152 00:07:55,260 --> 00:07:59,570 Don't be here now, Jack, left, exist, right, exist, push them. 153 00:07:59,850 --> 00:08:01,980 So this is 17 and this is 15. 154 00:08:02,520 --> 00:08:06,600 OK, now for the next level, change the value so its values now falls. 155 00:08:07,500 --> 00:08:12,300 Now we'll find out the size, so size of the queue is basically two sizes, too, so make of it. 156 00:08:12,320 --> 00:08:16,460 But again, size to first element will come here to come here. 157 00:08:16,530 --> 00:08:19,650 OK, so seven is the first element. 158 00:08:19,650 --> 00:08:21,920 Seven will come here now check. 159 00:08:22,290 --> 00:08:23,820 So left of seven exists. 160 00:08:23,820 --> 00:08:25,560 It is seven only so push seven. 161 00:08:26,010 --> 00:08:28,050 Right of seven exists it is eight. 162 00:08:28,050 --> 00:08:29,700 So push it now. 163 00:08:29,700 --> 00:08:30,750 This is the second element. 164 00:08:30,750 --> 00:08:31,590 So push 15. 165 00:08:33,409 --> 00:08:35,039 OK, very, very simple. 166 00:08:36,169 --> 00:08:38,299 Now, again, it will become true. 167 00:08:38,880 --> 00:08:40,770 OK, so we'll find out the size. 168 00:08:40,789 --> 00:08:43,620 So size is basically two, OK? 169 00:08:43,669 --> 00:08:47,860 So for 15, I forgot 20 exist, left, existing right exist. 170 00:08:47,870 --> 00:08:49,210 So Bush turned down 15. 171 00:08:49,760 --> 00:08:51,320 I am pushing 20 and 15. 172 00:08:51,350 --> 00:08:53,270 OK, now find out the size. 173 00:08:53,750 --> 00:08:56,660 So it size is basically four sizes four. 174 00:08:56,690 --> 00:08:58,700 So create a vector of space for. 175 00:09:01,510 --> 00:09:04,600 OK, the first element, the second element, third element in fourth element. 176 00:09:06,050 --> 00:09:12,360 Now, seven is the first element, so that I had seven here check left exist, yes, right exists to 177 00:09:12,380 --> 00:09:14,310 push them eight and nine. 178 00:09:15,110 --> 00:09:16,540 Now, this is the second element. 179 00:09:16,820 --> 00:09:18,830 So this is eight left exist. 180 00:09:18,840 --> 00:09:19,580 No right exist. 181 00:09:19,580 --> 00:09:20,810 No push. 182 00:09:20,810 --> 00:09:22,310 The third the third element. 183 00:09:23,650 --> 00:09:27,910 Now, Jack, so grunty recently, yes, so left exist. 184 00:09:29,230 --> 00:09:31,670 OK, so basically this was an audit, this was it. 185 00:09:31,700 --> 00:09:32,640 OK, so left exist. 186 00:09:32,680 --> 00:09:33,460 No right exist. 187 00:09:33,460 --> 00:09:33,650 No. 188 00:09:33,740 --> 00:09:37,510 OK, now I have 20 Sawchuk left exists. 189 00:09:37,510 --> 00:09:38,370 Right exists. 190 00:09:38,410 --> 00:09:39,970 So Bush 15 and 16. 191 00:09:43,220 --> 00:09:44,780 Now, Bob, 15. 192 00:09:46,140 --> 00:09:50,070 Right, 15 here, no left exist, no right exist. 193 00:09:50,100 --> 00:09:52,200 Yes, this is 22, right, 22 here. 194 00:09:54,070 --> 00:09:57,050 OK, now, again, change its value to false. 195 00:09:58,000 --> 00:10:00,880 Now find the size, so size is basically five. 196 00:10:02,340 --> 00:10:06,720 So this is basically, if you can see at this level, the number of nodes are five, so that's why the 197 00:10:06,720 --> 00:10:11,110 size is five one, two, three, four and five sizes five. 198 00:10:11,130 --> 00:10:14,640 I am calculating size and then I am making the vector of that size. 199 00:10:14,720 --> 00:10:15,060 OK. 200 00:10:17,030 --> 00:10:22,850 So at this level, the number of nodes was four, so my size was four at this, nor the number of levels 201 00:10:22,880 --> 00:10:24,140 the number of nodes was to. 202 00:10:24,290 --> 00:10:27,260 So my size of the vector was to add this level. 203 00:10:27,260 --> 00:10:29,900 The number of nodes was one, so the size was one. 204 00:10:30,470 --> 00:10:33,380 OK, now at this level the number of nodes are five. 205 00:10:33,380 --> 00:10:37,730 So that's why you can see the number of nodes are five, the size of the is five. 206 00:10:37,730 --> 00:10:39,770 So that's why I have to create a vector of size five. 207 00:10:39,800 --> 00:10:42,920 OK, so first element will come here, second element will come here. 208 00:10:42,920 --> 00:10:47,720 Third element will come here for Telemed will come here, fifth element will come here because the value 209 00:10:47,720 --> 00:10:48,230 is false. 210 00:10:49,290 --> 00:10:53,970 OK, so Bush got it so right here, here. 211 00:10:54,540 --> 00:10:57,990 OK, so this is it, left and right does not exist. 212 00:10:57,990 --> 00:11:03,870 So do nothing now pop nine so right nine here, left and right does not exist. 213 00:11:03,870 --> 00:11:04,470 Do nothing. 214 00:11:05,500 --> 00:11:12,970 Now, about 15, right, 15 here, so left exist, right exist 18 and 19, so 18 and 19. 215 00:11:14,410 --> 00:11:22,360 Now, pop, 16, right, 16 here, so left and right does not exist, pop 22, right, 22 here. 216 00:11:22,780 --> 00:11:24,910 So left and right does not exist. 217 00:11:24,910 --> 00:11:25,510 Do nothing. 218 00:11:26,750 --> 00:11:28,880 OK, so now find out the size. 219 00:11:29,030 --> 00:11:32,900 So first I will make it through, now find out the size of the council size. 220 00:11:32,900 --> 00:11:38,120 The sized is basically the face of the accused, basically to say, I will make a vector of size two. 221 00:11:38,630 --> 00:11:39,670 First element will come. 222 00:11:39,680 --> 00:11:42,150 Our second element will come here because the value is true. 223 00:11:42,540 --> 00:11:46,490 OK, you can see at this note to notice at present. 224 00:11:46,500 --> 00:11:49,120 So let's say size, vector size will be two. 225 00:11:49,160 --> 00:11:53,090 OK, so palpating right in here left exist. 226 00:11:53,090 --> 00:11:54,710 Right does not exist to push five. 227 00:11:55,520 --> 00:11:56,480 So push five. 228 00:11:57,640 --> 00:12:02,560 Now, Prop 19, right, 19 here, left and right, doesn't exist to do nothing. 229 00:12:02,740 --> 00:12:05,350 OK, now again, find out the size of the queue. 230 00:12:06,440 --> 00:12:07,820 Before we will make it false. 231 00:12:07,880 --> 00:12:11,210 OK, so the size of the queue is basically five, so make a vector. 232 00:12:11,960 --> 00:12:16,280 So OK, so size is basically one, so make a vector of size one. 233 00:12:16,280 --> 00:12:17,660 It will store only one element. 234 00:12:18,620 --> 00:12:19,370 Element five. 235 00:12:20,370 --> 00:12:23,490 So Bob Delamare, five, left and right, does not exist or do nothing. 236 00:12:23,520 --> 00:12:27,510 Finally, I would Google become embittered and we will stop gambling and we'll stop. 237 00:12:27,510 --> 00:12:28,490 And this is my answer. 238 00:12:29,440 --> 00:12:32,470 OK, this is my answer, you can see 20. 239 00:12:33,950 --> 00:12:42,070 Then I have 15 and seven and then I have seven, eight 2015, then I have 22, 16, 15, nine, and 240 00:12:42,530 --> 00:12:46,280 then I have 18 and 19 and then I have five. 241 00:12:46,440 --> 00:12:47,960 OK, very simple. 242 00:12:48,260 --> 00:12:48,870 Understood. 243 00:12:49,420 --> 00:12:50,700 Now let us write the code. 244 00:12:50,780 --> 00:12:53,180 OK, so the code is going to be very, very simple. 245 00:12:53,210 --> 00:12:56,290 This will be very similar to the level traversal. 246 00:12:56,360 --> 00:12:56,720 OK. 247 00:12:58,170 --> 00:13:06,000 Now, let us write the code again so we have to return to profitability, just so, let us create our 248 00:13:06,000 --> 00:13:06,410 answer. 249 00:13:09,720 --> 00:13:14,640 So the prospect of integers, let's name it, we you can name it, result also. 250 00:13:14,670 --> 00:13:17,450 OK, so let's name it result. 251 00:13:17,460 --> 00:13:18,750 This will store our result. 252 00:13:18,780 --> 00:13:21,020 OK, now the best case. 253 00:13:21,420 --> 00:13:23,760 So if basically route is null. 254 00:13:25,190 --> 00:13:31,340 That ministry is empty, so, my --, I will also be empty so I can return here. 255 00:13:31,460 --> 00:13:34,030 OK, now again, I was code. 256 00:13:34,220 --> 00:13:35,180 We will make you. 257 00:13:36,280 --> 00:13:40,630 Now, this time, you will again be of North Star, because I have to check for left and right. 258 00:13:41,530 --> 00:13:44,680 OK, so Guilfoile, North Star, let's name it. 259 00:13:44,720 --> 00:13:51,070 Q So to start the full loop, I have to push the Rudimental to push Bushrod Standard called. 260 00:13:51,580 --> 00:13:54,100 Now, I told you I have to take a variable left. 261 00:13:54,140 --> 00:13:54,460 Right. 262 00:13:54,460 --> 00:13:55,000 So bool. 263 00:13:56,380 --> 00:13:57,340 Left to right. 264 00:13:57,760 --> 00:13:59,950 OK, so initially this will be through. 265 00:14:01,580 --> 00:14:03,350 I will constantly change its value. 266 00:14:03,380 --> 00:14:03,730 OK. 267 00:14:05,370 --> 00:14:07,760 So this is the variable bull left-to-right. 268 00:14:07,770 --> 00:14:09,360 I will constantly change its value. 269 00:14:09,870 --> 00:14:15,110 Now what we have to do, so our standard condition value is not empty. 270 00:14:15,120 --> 00:14:16,500 I have to do some work. 271 00:14:17,430 --> 00:14:18,510 I have to do some work. 272 00:14:18,540 --> 00:14:21,460 OK, so what is the work that I have to do? 273 00:14:21,480 --> 00:14:25,370 So if we can see carefully, first of all, I am calculating the size. 274 00:14:26,010 --> 00:14:29,110 I am calculating the size of the queue and then I am preparing my vector. 275 00:14:29,160 --> 00:14:29,470 OK. 276 00:14:29,490 --> 00:14:32,730 So find the size and make a vector of that size. 277 00:14:33,660 --> 00:14:35,630 Make a vector of that size. 278 00:14:35,690 --> 00:14:36,030 OK. 279 00:14:37,660 --> 00:14:39,760 So first, let us find out the size of the. 280 00:14:40,030 --> 00:14:43,990 How many elements are present at this point inside the cube? 281 00:14:44,020 --> 00:14:46,240 OK, so this is good size. 282 00:14:47,680 --> 00:14:53,590 So what it will return me, so basically it will return me at this level, how many nodes are present? 283 00:14:53,620 --> 00:15:01,200 OK, so the size so good our size means how many nodes are present at this level. 284 00:15:02,970 --> 00:15:03,300 OK. 285 00:15:04,360 --> 00:15:08,320 So this is the meaning of size, how many roles are present at this level? 286 00:15:08,380 --> 00:15:18,250 OK, now I will create a vector of that size so that part of integers, let's name Mitro, OK, because 287 00:15:18,700 --> 00:15:21,370 Romy's so basically this is the first rule. 288 00:15:22,680 --> 00:15:27,570 This is the second, OK, and this is the third rule, so let's name it so you can name it anything. 289 00:15:27,600 --> 00:15:29,730 OK, I have to create a vector. 290 00:15:30,820 --> 00:15:31,640 Of this size. 291 00:15:31,690 --> 00:15:34,940 OK, so this size is basically the sunglasses, OK? 292 00:15:35,470 --> 00:15:36,100 You can see. 293 00:15:37,070 --> 00:15:41,010 So this is phase one, that process to, again, victory phase two. 294 00:15:41,060 --> 00:15:41,410 OK. 295 00:15:42,370 --> 00:15:48,350 So after creating director directorate, I have to do so basically I have to pop I have to pop size 296 00:15:48,350 --> 00:15:50,750 element, so let us pop the element. 297 00:15:51,800 --> 00:15:57,140 So I have to publicize elements, OK, I have to publicize elements. 298 00:15:59,980 --> 00:16:05,110 Now, what we are doing so at this point, what we are doing, we are traversing the current level. 299 00:16:07,040 --> 00:16:13,250 Traversing current level, OK, we are traversing the current level because in the current level, how 300 00:16:13,250 --> 00:16:16,450 many nodes are present size and all that present? 301 00:16:16,490 --> 00:16:21,360 So I am traversing FaceTime, so that means I am traversing the current level. 302 00:16:21,430 --> 00:16:24,470 OK, I am traversing the current level to. 303 00:16:25,380 --> 00:16:32,760 Let us pop out different element, so Renauld Star F is basically good old friend. 304 00:16:35,500 --> 00:16:39,150 OK, and good artpop, otherwise we will get family mutex. 305 00:16:39,460 --> 00:16:40,110 OK, good. 306 00:16:40,270 --> 00:16:41,100 Pop is necessary. 307 00:16:41,920 --> 00:16:43,350 Now I have to decide. 308 00:16:43,390 --> 00:16:50,410 OK, so at this point what I have to do, so I have to decide whether I have to fill this out in this 309 00:16:50,410 --> 00:16:52,790 way or I have to fill the vacuum in this way. 310 00:16:52,860 --> 00:16:54,470 OK, I have to decide. 311 00:16:54,760 --> 00:16:56,620 So how we can decide. 312 00:16:56,620 --> 00:16:59,110 We can decide with the help of this left-to-right. 313 00:16:59,310 --> 00:17:02,820 OK, so basically this is SKU. 314 00:17:03,220 --> 00:17:05,260 OK, these are some elements. 315 00:17:05,650 --> 00:17:07,930 So first element, this has two choices. 316 00:17:08,230 --> 00:17:14,200 Either it will come at this point, basically at this starting point or it will come at the ending point. 317 00:17:15,109 --> 00:17:22,490 OK, either the first element will come at this starting point, if left to right is basically true, 318 00:17:22,790 --> 00:17:26,460 if left right is basically false, it will come at the last weekend. 319 00:17:26,480 --> 00:17:30,030 OK, so let's find out the index of the first element. 320 00:17:30,050 --> 00:17:31,640 Let us find out its index. 321 00:17:32,090 --> 00:17:36,730 So its index will be zero or its index will be basically Saiz minus one. 322 00:17:36,770 --> 00:17:38,510 OK, size minus one means this one. 323 00:17:39,050 --> 00:17:39,840 The last index. 324 00:17:39,860 --> 00:17:40,130 OK. 325 00:17:41,330 --> 00:17:50,980 So let us find out the correct position for the settlement, so, OK, so basically let us use the operator. 326 00:17:50,990 --> 00:17:53,120 OK, so Left-to-right. 327 00:17:56,080 --> 00:17:59,760 So if left to right is basically so I'm using the radio operator. 328 00:17:59,810 --> 00:18:01,530 So if Left-to-right is true. 329 00:18:02,580 --> 00:18:03,810 Then Texas A. 330 00:18:05,510 --> 00:18:11,420 If we have to right this falls, then its index is basically says minus one, minus a. 331 00:18:12,750 --> 00:18:15,990 OK, and then what they will do after finding out the correct. 332 00:18:16,020 --> 00:18:20,670 Next, let's push the current element at its right index. 333 00:18:20,700 --> 00:18:23,250 OK, so this is ephemeral value. 334 00:18:24,120 --> 00:18:24,840 Very simple. 335 00:18:25,840 --> 00:18:29,530 And then if left exist, Bush left, if right exist, Bush right. 336 00:18:30,510 --> 00:18:31,680 This is standard code. 337 00:18:31,720 --> 00:18:36,900 OK, so if left exist, so culotte Bush left. 338 00:18:38,360 --> 00:18:39,980 Similarly, airfreighted exist. 339 00:18:42,810 --> 00:18:44,250 Then Guillard Bushrod. 340 00:18:47,470 --> 00:18:54,970 OK, so what I'm doing here is so I told you, I suppose this is the cue, OK, this is the cue and. 341 00:18:56,700 --> 00:19:03,870 So the first element of the Q so this first element can come here or the first element come can come 342 00:19:03,870 --> 00:19:09,180 here if they're left to prove a loose fault, if we have to prove is true, then it will come here. 343 00:19:09,180 --> 00:19:10,530 Otherwise it will come here. 344 00:19:10,560 --> 00:19:12,720 OK, so basically this is to the. 345 00:19:13,380 --> 00:19:14,620 This the radio operator. 346 00:19:14,940 --> 00:19:19,290 So if it is true, then this line will be executed. 347 00:19:19,290 --> 00:19:22,080 If this is false, then this line will be executed. 348 00:19:22,530 --> 00:19:24,390 OK, I'm repeating myself. 349 00:19:24,900 --> 00:19:26,590 So intracerebral know what happens. 350 00:19:26,610 --> 00:19:32,370 So if this condition is true, if it is true, then I will execute this line. 351 00:19:32,940 --> 00:19:38,430 And if this is false, if this is false, I will execute this line after this column. 352 00:19:38,700 --> 00:19:40,860 OK, after this column, I will execute this line. 353 00:19:41,100 --> 00:19:45,300 So what I am doing, I am trying to find out the right index for the current element. 354 00:19:45,330 --> 00:19:50,290 OK, so after finding out the right index, I am pushing the limit. 355 00:19:50,310 --> 00:19:51,150 So this is the element. 356 00:19:51,150 --> 00:19:52,950 I am pushing the element to it. 357 00:19:52,950 --> 00:19:53,700 Right index. 358 00:19:53,910 --> 00:19:56,160 OK, and then this is standard. 359 00:19:56,160 --> 00:19:58,350 If left exist, push left or right exist. 360 00:19:58,350 --> 00:19:58,920 Both right. 361 00:19:59,340 --> 00:19:59,730 OK. 362 00:20:02,590 --> 00:20:04,540 So after traversing the current level. 363 00:20:04,870 --> 00:20:06,880 OK, so the current level has been finished. 364 00:20:07,120 --> 00:20:09,680 OK, so current level has been finished. 365 00:20:09,700 --> 00:20:12,800 So basically now let us reach the next level. 366 00:20:13,480 --> 00:20:15,130 So after the current level. 367 00:20:16,430 --> 00:20:22,220 So after the current level traversal is done, what I have to do, I have to change the value of Left-to-right, 368 00:20:22,220 --> 00:20:23,870 I have to make it false. 369 00:20:23,870 --> 00:20:26,200 If it was true, I have to make it true. 370 00:20:26,210 --> 00:20:27,170 If it was false. 371 00:20:27,200 --> 00:20:30,950 OK, so Left-to-right is basically equal to. 372 00:20:31,990 --> 00:20:33,310 Rivers of Left-to-right. 373 00:20:38,520 --> 00:20:44,530 OK, so after the current level of the current level has been reversed and its output has been stored, 374 00:20:44,610 --> 00:20:46,660 but I have to do I have to change the value. 375 00:20:46,680 --> 00:20:49,290 So if Left-to-right was true, it will become false. 376 00:20:49,410 --> 00:20:53,040 OK, OK, so if the left right was true, it will become false. 377 00:20:53,310 --> 00:20:55,650 If the left-to-right was false, it will become true. 378 00:20:55,720 --> 00:20:56,040 OK. 379 00:20:57,010 --> 00:21:01,840 So I'm changing the value of left to right now after changing the value of Left-to-right. 380 00:21:03,240 --> 00:21:08,250 Let us push the current level inside our research director, so deserted Dot. 381 00:21:09,260 --> 00:21:09,900 Push back. 382 00:21:12,050 --> 00:21:14,060 What is my answer so ruys, my answer. 383 00:21:14,090 --> 00:21:14,390 OK. 384 00:21:16,400 --> 00:21:18,760 You can see it clearly, so this is it. 385 00:21:18,920 --> 00:21:23,320 I am pushing all inside this one, OK, so it is at least containing my answer. 386 00:21:23,450 --> 00:21:27,070 So it is Eldard push becquerel, OK, because this level has been finished. 387 00:21:27,470 --> 00:21:32,440 So after traversing the current level, let us push the current level into our answer. 388 00:21:33,770 --> 00:21:39,470 And finally, when the will become embittered and will break, I can return desert. 389 00:21:40,940 --> 00:21:44,300 OK, so this is the complete code now, alerts are now called. 390 00:21:50,030 --> 00:21:51,380 OK, so now let's meet. 391 00:21:56,520 --> 00:21:58,530 OK, so our goal is hundred percent correct. 392 00:21:58,560 --> 00:22:02,370 Now, let us take a very small example and let us read another code. 393 00:22:02,430 --> 00:22:05,450 OK, so let us take very small example. 394 00:22:05,460 --> 00:22:11,580 So I have three, then let's in nine the example given indication, OK, 15 and seven on. 395 00:22:12,150 --> 00:22:13,920 I'm taking a very small example. 396 00:22:13,980 --> 00:22:15,480 OK, so cute. 397 00:22:15,480 --> 00:22:17,800 Or Bushrod and Left-to-right value is true. 398 00:22:17,900 --> 00:22:20,040 OK, so basically this is the dequeue. 399 00:22:21,260 --> 00:22:28,520 It is containing only one element, which is tree, OK, and this value, so left to right value is 400 00:22:28,520 --> 00:22:32,120 basically true at this point is not empty. 401 00:22:32,130 --> 00:22:33,060 Find out the size. 402 00:22:33,080 --> 00:22:35,810 So size is basically one size is basically one. 403 00:22:36,050 --> 00:22:37,580 Make a vector of size one. 404 00:22:38,480 --> 00:22:40,430 So I am making a vector of size one. 405 00:22:40,430 --> 00:22:43,250 So this is a vector of size one. 406 00:22:43,340 --> 00:22:47,960 OK, now I lost the current level so size the value size is one. 407 00:22:48,200 --> 00:22:51,190 So but I was the current level which is three only. 408 00:22:51,230 --> 00:22:53,510 OK, it is containing only one element which is three. 409 00:22:53,990 --> 00:22:57,290 So get different elements of different elements of pop the element. 410 00:22:58,290 --> 00:23:04,110 Now find out the index, so left right values basically true, so the value of five will be zero and 411 00:23:04,110 --> 00:23:05,620 basically the index will be zero. 412 00:23:05,760 --> 00:23:09,990 OK, the index is zero rule of Index 040. 413 00:23:10,020 --> 00:23:11,130 So this is the rule of zero. 414 00:23:11,430 --> 00:23:12,960 It is containing the value three. 415 00:23:13,050 --> 00:23:15,200 OK, now check left exist. 416 00:23:15,480 --> 00:23:17,640 Yes, nine exist to push nine. 417 00:23:18,840 --> 00:23:22,350 Now, right, exist, yes, it is 20, so push 20. 418 00:23:23,750 --> 00:23:27,210 OK, and now the current level has been finished. 419 00:23:27,230 --> 00:23:30,150 OK, so this was the current level, the current level has been finished. 420 00:23:30,290 --> 00:23:33,230 I am changing the value of Left-to-right so it will become false. 421 00:23:34,580 --> 00:23:41,360 And I am pushing the arrow in the result that, OK, so this is the result of a bigger one. 422 00:23:42,660 --> 00:23:43,800 So this has been pushed. 423 00:23:43,840 --> 00:23:48,300 OK, so this small role has been pushed, Zimbelman. 424 00:23:48,560 --> 00:23:51,170 Now, again, the queue is not empty. 425 00:23:51,210 --> 00:23:53,040 It is containing Element 1920. 426 00:23:53,070 --> 00:23:54,340 Now let us find out the site. 427 00:23:54,600 --> 00:23:59,140 So this team decides is to OK, nine and 28 is containing the element. 428 00:23:59,610 --> 00:24:01,100 So the site is basically two. 429 00:24:01,710 --> 00:24:04,740 You can see at this level, two nodes are present. 430 00:24:04,830 --> 00:24:07,420 OK, so now let us reverse the current level. 431 00:24:07,440 --> 00:24:10,230 So in the current level, 1920, they are two nodes. 432 00:24:10,290 --> 00:24:12,150 OK, so four I called you. 433 00:24:12,150 --> 00:24:14,700 I left inside the various sizes, basically two. 434 00:24:15,180 --> 00:24:16,980 So I will loop will run two times. 435 00:24:17,220 --> 00:24:19,340 OK does get different elements. 436 00:24:19,340 --> 00:24:20,080 So this is different. 437 00:24:20,400 --> 00:24:21,970 Nine nine is different. 438 00:24:22,410 --> 00:24:29,170 OK, so one thing, I have created a vector of size two so this is my vector of size to. 439 00:24:29,380 --> 00:24:32,400 OK now Bob the front element this is nine. 440 00:24:33,460 --> 00:24:34,820 Now, let's find this index. 441 00:24:34,840 --> 00:24:36,900 OK, so left-to-right value is basically false. 442 00:24:37,600 --> 00:24:38,530 So this is false. 443 00:24:38,740 --> 00:24:40,180 This will be my index. 444 00:24:40,180 --> 00:24:43,270 So says the value of is to soar to minus one. 445 00:24:43,420 --> 00:24:44,650 The value of is zero. 446 00:24:44,770 --> 00:24:46,540 OK, so this is basically one. 447 00:24:46,870 --> 00:24:48,370 So I will push nine here. 448 00:24:49,370 --> 00:24:54,680 Bush nine here now check Jack, left and right of nine exist, no, it does not exist, so do nothing. 449 00:24:55,080 --> 00:24:59,180 OK, now what will happen this little pestilential times? 450 00:24:59,390 --> 00:25:02,330 So let us run this loop one more time now, Bob. 451 00:25:02,330 --> 00:25:06,120 Twenty, find the index of 20, so find the index. 452 00:25:06,530 --> 00:25:09,170 So this is basically sizes two minus one. 453 00:25:09,170 --> 00:25:10,460 The value of A is one. 454 00:25:10,520 --> 00:25:12,330 OK, so it's index zero. 455 00:25:12,350 --> 00:25:13,760 So I have to push that index zero. 456 00:25:14,150 --> 00:25:16,760 I have to push Rohloff index value. 457 00:25:16,760 --> 00:25:18,080 So low of zero is value. 458 00:25:18,080 --> 00:25:20,000 I lose 20, so I will push 20 here. 459 00:25:20,940 --> 00:25:25,840 OK, and then left exist, right exist, so yes, 15 and seven exists to push them. 460 00:25:25,860 --> 00:25:31,920 So I have 15 and seven, OK, Bush 15 and seven then, but I will do so after traversing the current 461 00:25:31,920 --> 00:25:32,190 level. 462 00:25:32,490 --> 00:25:33,750 Current level has been finished. 463 00:25:34,470 --> 00:25:35,690 After trouncing the current level. 464 00:25:35,700 --> 00:25:41,400 I am changing the value of Left-to-right so it will become true again and I'm pushing my role in that. 465 00:25:42,120 --> 00:25:47,940 OK, so this is the situation of my electorate as containing three then it is containing twenty nine. 466 00:25:49,060 --> 00:25:55,660 OK, now, again, what we will do so find out the sides, find out the sides, you can see I am finding 467 00:25:55,660 --> 00:25:58,080 out the size and then create a vector of that size. 468 00:25:58,570 --> 00:26:01,120 So find out the size and create a vector of that size. 469 00:26:01,130 --> 00:26:06,880 So I will create a process to then pop different element, which is 15, find the right index with the 470 00:26:06,880 --> 00:26:07,510 help of this. 471 00:26:08,530 --> 00:26:11,660 Left right values, basically true, so the index is basically zero. 472 00:26:11,680 --> 00:26:15,720 So I will push 15 here left and right of 15 does not exist. 473 00:26:15,730 --> 00:26:17,590 So do nothing then Bob. 474 00:26:17,620 --> 00:26:22,210 The next element seven right index is basically the value of AI is basically one. 475 00:26:22,600 --> 00:26:26,230 So put seven here, then left and right does not exist. 476 00:26:26,230 --> 00:26:28,000 So left and right does not exist. 477 00:26:28,360 --> 00:26:31,670 Then what I will do so change the value of left right. 478 00:26:31,670 --> 00:26:37,930 So it will become false again, then push this inside the vector so it will become fifteen and seven. 479 00:26:40,180 --> 00:26:44,430 And then what I'm doing here is so if you will go up, the queue is now empty. 480 00:26:44,710 --> 00:26:46,150 OK, who is now empty? 481 00:26:46,150 --> 00:26:47,290 And then I am returning my. 482 00:26:47,800 --> 00:26:48,890 So this is my result. 483 00:26:49,690 --> 00:26:51,850 This is my desert and I will return this result. 484 00:26:51,880 --> 00:26:55,440 OK, so this is the complete logic and the complete Driton. 485 00:26:55,480 --> 00:26:58,660 OK, so what is the time and the space complexities of time? 486 00:26:58,660 --> 00:26:59,860 Complexity is just big. 487 00:26:59,860 --> 00:27:03,010 Often we are going through each and every now and again. 488 00:27:03,310 --> 00:27:05,140 The space complexity is also big. 489 00:27:05,140 --> 00:27:07,270 Often we are using you OK. 490 00:27:09,230 --> 00:27:10,940 So this is basically the complete. 491 00:27:11,330 --> 00:27:16,350 OK, now this is a new technique, this technique will be used many times. 492 00:27:16,370 --> 00:27:18,180 OK, so traversing the current level. 493 00:27:18,560 --> 00:27:24,620 So how are you going to basically find out the size, make a vector of that size and reverse the current 494 00:27:24,620 --> 00:27:24,890 level? 495 00:27:24,920 --> 00:27:28,400 OK, so this is a new technique that we have not seen before. 496 00:27:28,430 --> 00:27:30,880 OK, traversing the levels. 497 00:27:30,940 --> 00:27:33,790 OK, we are traversing the compute levels three dendrobium. 498 00:27:33,810 --> 00:27:37,040 We are introducing nine and 20, then I'm turning 15 and seven. 499 00:27:37,070 --> 00:27:42,770 OK, so this is new technique, finding out the size and then reversing the current level. 500 00:27:43,040 --> 00:27:46,130 OK, so if you have any doubt in this question you can ask me. 501 00:27:46,150 --> 00:27:46,640 Thank you.