1 00:00:01,290 --> 00:00:01,950 Hi, everyone. 2 00:00:01,980 --> 00:00:08,670 So in this video, we are going to discuss the situation, reverse level order timeously. 3 00:00:10,230 --> 00:00:13,750 OK, so this is very same this is very similar to the previous question. 4 00:00:13,770 --> 00:00:17,520 Now, the only difference is basically I will perform the LEVEL-HEADED reversal. 5 00:00:17,990 --> 00:00:20,730 We will perform the level traversal, but in reverse v.. 6 00:00:21,120 --> 00:00:24,180 OK, believer's I mean, from bottom to top. 7 00:00:24,660 --> 00:00:27,600 Again, normal level is basically from top to bottom. 8 00:00:27,900 --> 00:00:30,300 Reverse is basically from bottom to top. 9 00:00:31,260 --> 00:00:32,980 OK, so what will be our output? 10 00:00:33,000 --> 00:00:34,200 Consider this example. 11 00:00:34,410 --> 00:00:35,570 So from bottom to top. 12 00:00:35,580 --> 00:00:36,870 So seven. 13 00:00:38,150 --> 00:00:46,970 Then I have nine and eight, so nine and then two and then so two and ten and then I have one, so basically 14 00:00:46,970 --> 00:00:47,190 one. 15 00:00:47,290 --> 00:00:50,930 OK, so this is the reverse level of the traversal. 16 00:00:52,780 --> 00:00:54,010 I think about the logic. 17 00:00:54,050 --> 00:01:01,810 OK, now consider this example, so it's traversal basically from top to down reverses, basically from 18 00:01:01,810 --> 00:01:02,640 bottom to top. 19 00:01:03,020 --> 00:01:04,239 OK, so from bottom. 20 00:01:04,250 --> 00:01:06,760 So does this drill then? 21 00:01:06,760 --> 00:01:15,160 I have tenanted, so I have 10 and eight, then I have 21 and seven, 21 and seven, and then I have 22 00:01:15,160 --> 00:01:15,640 50. 23 00:01:15,640 --> 00:01:16,900 So I have 50. 24 00:01:17,970 --> 00:01:19,630 OK, very, very simple. 25 00:01:19,650 --> 00:01:22,360 So this is the reverse level of the traversal. 26 00:01:23,550 --> 00:01:25,770 OK, now let us see how we can. 27 00:01:27,470 --> 00:01:28,390 So I'll just caution. 28 00:01:28,410 --> 00:01:30,480 So this is going to be very similar approach. 29 00:01:30,530 --> 00:01:33,260 OK, very similar approach we will take the help of. 30 00:01:34,490 --> 00:01:37,440 We need you to perform the level of the traversal. 31 00:01:38,210 --> 00:01:39,050 This is very simple. 32 00:01:39,060 --> 00:01:40,830 We need you to perform diversity. 33 00:01:41,210 --> 00:01:43,280 So apart from you, where do we lose? 34 00:01:43,280 --> 00:01:45,990 We will use back to store our answer. 35 00:01:46,080 --> 00:01:49,510 OK, Stack to store our answer, we will not likely print. 36 00:01:50,240 --> 00:01:52,720 OK, so let us consider an example. 37 00:01:52,730 --> 00:01:56,300 So this is, let's say five, 10, 12, seven and eight. 38 00:01:56,930 --> 00:02:03,590 OK, so first let us write the simple logic code, simple level, whatever sort of simple level or traversal 39 00:02:03,590 --> 00:02:10,759 says while your queue is not empty, you get a different element, you get a different element, you 40 00:02:10,759 --> 00:02:12,670 bring different element. 41 00:02:13,130 --> 00:02:18,560 And then if the left exist, push right, push left. 42 00:02:18,770 --> 00:02:21,560 And similarly, you will check if right exist. 43 00:02:22,840 --> 00:02:27,790 So Bush, right, this is simple level reversal from top to down. 44 00:02:28,070 --> 00:02:31,310 OK, but here we have to perform the reverse level reversal. 45 00:02:31,570 --> 00:02:34,900 So what we will do so instead of printing here. 46 00:02:36,110 --> 00:02:40,100 Instead of the sprinting, what will look, we will store the answer in Stack. 47 00:02:41,420 --> 00:02:47,390 We will store the answer in Steck, so basically if you perform the level, but I was a low key performance 48 00:02:47,390 --> 00:02:52,340 level traversal, what will really bring to the value, OK, what will be the output if you perform 49 00:02:52,340 --> 00:02:53,640 the simple laboratory? 50 00:02:53,990 --> 00:02:57,260 So this will be five, then 10, 12 and then seven, eight. 51 00:02:57,850 --> 00:02:59,060 OK, if you will print. 52 00:02:59,450 --> 00:03:00,440 If I am printing. 53 00:03:00,440 --> 00:03:04,660 So this will be five, then 10 and then one and then seven and eight. 54 00:03:05,180 --> 00:03:09,560 And what I'm saying here is basically instead of printing stored it in the stack. 55 00:03:10,600 --> 00:03:11,650 Store it in a stick. 56 00:03:11,680 --> 00:03:16,220 So how will the store, first of all, five welcome, then 10, then 12, then seven and eight. 57 00:03:16,510 --> 00:03:18,220 So basically this will be my steak. 58 00:03:19,260 --> 00:03:22,890 Five, then 10, then 12, then seven and then eight. 59 00:03:24,140 --> 00:03:26,000 OK, this will be Lastic. 60 00:03:27,160 --> 00:03:32,830 OK, so when this loop will end, when the queue will become empty, so what I will write here, so 61 00:03:32,830 --> 00:03:38,430 I will pop all the elements from the stack bop, all element from stack and print up. 62 00:03:38,470 --> 00:03:39,430 All element from. 63 00:03:40,380 --> 00:03:41,880 The Steck and Brent. 64 00:03:44,410 --> 00:03:52,060 So every single element, so pop it and I pop seven, pop 12, pop, pop five, so this will be eight 65 00:03:52,420 --> 00:03:56,930 seven, then I have 12, then I have 10 and then I have five. 66 00:03:57,190 --> 00:04:00,970 OK, so this is basically the reverse level order traversal. 67 00:04:03,460 --> 00:04:11,590 OK, now one thing, if you look carefully, it's the reverse order traversal is basically five, traversal 68 00:04:11,680 --> 00:04:16,600 is basically seven, then it then 10, then 12 and then five. 69 00:04:17,019 --> 00:04:18,870 But I'm getting answer wrong here. 70 00:04:18,880 --> 00:04:20,709 Basically, eight and seven are slabbed. 71 00:04:22,000 --> 00:04:22,690 Well, and then. 72 00:04:23,380 --> 00:04:26,680 OK, if you will see, so basically this answer is wrong. 73 00:04:27,640 --> 00:04:30,210 OK, so how we can make this answer correct? 74 00:04:30,430 --> 00:04:31,960 How are we going to make this answer correct? 75 00:04:32,020 --> 00:04:34,000 So basically, I will change this old. 76 00:04:34,900 --> 00:04:37,150 I will change the order of these two lines. 77 00:04:37,540 --> 00:04:41,860 OK, so at first I am checking if left exist, then Bush left. 78 00:04:42,430 --> 00:04:45,620 So basically Ben is getting pushed first before 12. 79 00:04:46,210 --> 00:04:49,780 But what I want I want to come first and then Ben. 80 00:04:50,200 --> 00:04:51,700 So I will change this order. 81 00:04:52,120 --> 00:04:52,630 So I will. 82 00:04:52,630 --> 00:04:54,840 Right if right. 83 00:04:54,850 --> 00:04:57,100 Exist then Bush. 84 00:04:57,100 --> 00:04:57,490 Right. 85 00:04:58,590 --> 00:05:07,470 If left exist, so Bush left, so after changing the order, after writing this quote, this output 86 00:05:07,470 --> 00:05:10,410 will be changed to first five will welcome, then 12. 87 00:05:10,410 --> 00:05:13,970 Well, welcome, then 10 will come, then it will come and the sound will come. 88 00:05:13,980 --> 00:05:14,840 It is very simple. 89 00:05:15,390 --> 00:05:19,080 So initially what I was checking first left existed, then Bush left. 90 00:05:19,080 --> 00:05:21,960 But here what I will do first I will check. 91 00:05:21,960 --> 00:05:22,300 Right. 92 00:05:22,320 --> 00:05:26,720 So if will exist then Bush 12 first if left exist. 93 00:05:26,730 --> 00:05:28,080 So then Bush left. 94 00:05:28,650 --> 00:05:30,780 If right to exist then Bush right. 95 00:05:31,350 --> 00:05:33,370 If left exist then Bush left. 96 00:05:34,090 --> 00:05:36,490 OK, so basically I will change the order. 97 00:05:36,560 --> 00:05:38,090 OK, so this will be my new order. 98 00:05:38,280 --> 00:05:42,810 So if this is my new order, this will be my new output, this will be my new output. 99 00:05:42,810 --> 00:05:49,530 And if I will store this output in stack, if I was told this output instead it will be five, then 100 00:05:49,530 --> 00:05:52,830 12, then ten, then eight and then seven. 101 00:05:53,260 --> 00:05:58,680 OK, and if I will pop every single element from the stack, bop every single element from the stack, 102 00:05:58,680 --> 00:06:01,720 so it will be seven, eight, 10, 12 and five. 103 00:06:01,800 --> 00:06:07,140 OK, so it will be seven, eight, 10, 12 and five. 104 00:06:07,360 --> 00:06:09,030 OK, this is the right answer. 105 00:06:09,060 --> 00:06:09,840 You can compare. 106 00:06:11,880 --> 00:06:13,540 OK, you can compare. 107 00:06:14,440 --> 00:06:17,160 So what we have to do, we have to do minor, minor changes. 108 00:06:17,550 --> 00:06:22,710 So what is a minor changes first, instead of printing the value, what I will do, I will store it 109 00:06:22,710 --> 00:06:23,310 in a stack. 110 00:06:23,910 --> 00:06:25,620 This is the first change that we have to do. 111 00:06:26,010 --> 00:06:28,670 Second change is basically I have to reverse the order. 112 00:06:29,160 --> 00:06:30,270 I have to reverse this order. 113 00:06:30,270 --> 00:06:33,270 First I will check for right, then I will check for left. 114 00:06:34,260 --> 00:06:39,660 OK, so this is the second change, 13, just basically when the queues empty, all the elements are 115 00:06:39,660 --> 00:06:41,480 basically present inside the stack. 116 00:06:41,700 --> 00:06:42,610 So what you have to do. 117 00:06:42,780 --> 00:06:46,370 You have to pop all the elements from the stack and then print. 118 00:06:46,800 --> 00:06:50,340 OK, so basically what will be the time and the space complexity? 119 00:06:50,670 --> 00:06:52,890 So again, the time complexity is big. 120 00:06:52,890 --> 00:06:59,730 Often we are just iterating over all the nodes and space complexities big, often for queue and big 121 00:06:59,730 --> 00:07:00,690 often for Steg. 122 00:07:00,690 --> 00:07:07,250 So ultimately the time and the space complexity, they both seem, they both are big, often OK. 123 00:07:08,370 --> 00:07:09,720 They both are big often. 124 00:07:11,250 --> 00:07:13,470 So I hope you understood the logic and the question. 125 00:07:13,660 --> 00:07:16,500 OK, so now let's write the code, OK? 126 00:07:18,800 --> 00:07:23,180 So here this is the binded trailer traversal part two. 127 00:07:23,450 --> 00:07:26,930 OK, this is called in reverse order traversal bottom up level. 128 00:07:26,930 --> 00:07:27,620 Order traversal. 129 00:07:27,800 --> 00:07:28,160 OK. 130 00:07:29,520 --> 00:07:35,290 So basically what we have to do, so this is the second part of the question, this is a reversal of 131 00:07:35,310 --> 00:07:39,690 that reversal, but according to the question, they are calling it a bottom up level reversal. 132 00:07:39,750 --> 00:07:46,440 OK, what are some bottom up level traversal level order will now see? 133 00:07:46,890 --> 00:07:53,040 So if this is the input, this is my output first 15 and 17, nine and 20 and then three. 134 00:07:53,100 --> 00:07:53,450 OK. 135 00:07:54,840 --> 00:08:00,090 But if you will recall from the last problem, what is our output, so we are storing the output in 136 00:08:00,090 --> 00:08:01,440 this very first level one. 137 00:08:02,700 --> 00:08:03,660 Then level two. 138 00:08:04,640 --> 00:08:08,780 Nine and 20, and then I'm starting level three, which is 15 and seven. 139 00:08:10,140 --> 00:08:14,340 So if I will ride my old cold, OK, so this is the output. 140 00:08:15,620 --> 00:08:20,360 This is the output from our last call, from our last problem. 141 00:08:20,410 --> 00:08:24,750 OK, this is the output from our last problem and if you will compare. 142 00:08:25,010 --> 00:08:27,980 So basically this output is just the reverse. 143 00:08:29,650 --> 00:08:35,890 OK, so what we will do, I will write the old code, OK, we will use our old code and just we will 144 00:08:35,890 --> 00:08:36,980 reverse our output. 145 00:08:37,659 --> 00:08:39,960 OK, so reverse our oil output. 146 00:08:40,960 --> 00:08:46,460 It was all output and you will get the new output, you will get the new output. 147 00:08:46,750 --> 00:08:51,570 So after reversing this, after reversing this, 15 and seven will come along. 148 00:08:52,270 --> 00:08:55,810 Then I have nine and twenty and then three will come. 149 00:08:55,840 --> 00:09:01,810 OK, so here in this question, what we have to do, our old output, our old code, and just we will 150 00:09:01,810 --> 00:09:03,010 use reverse function. 151 00:09:03,040 --> 00:09:04,630 OK, now let's see. 152 00:09:07,710 --> 00:09:13,020 So basically, this is the old question, this is this simple traversal, OK, this is the old question. 153 00:09:13,020 --> 00:09:14,730 What will letters copy, the so-called. 154 00:09:17,190 --> 00:09:20,610 Let's copy this code and let's it hit. 155 00:09:22,410 --> 00:09:29,340 OK, so this is our old code and what we have written, so instead of returning normal answered. 156 00:09:30,240 --> 00:09:35,600 What we have to do, we have to reverse our output, so let us so reverses in malfunction. 157 00:09:35,850 --> 00:09:38,520 It will take two things as inputs starting and end. 158 00:09:38,670 --> 00:09:40,320 So starting is we not begin. 159 00:09:41,380 --> 00:09:42,860 These starting my output. 160 00:09:42,880 --> 00:09:46,750 So starting will be the dowbiggin ending will be redundant. 161 00:09:48,270 --> 00:09:53,850 OK, so this liver function will take two things from two things, OK, from where to where I have to 162 00:09:53,850 --> 00:09:54,270 reverse. 163 00:09:55,640 --> 00:09:59,240 So basically, this reverse function, this reverse function. 164 00:10:00,800 --> 00:10:04,800 It takes tooting the starting point and the ending point, OK? 165 00:10:04,820 --> 00:10:07,910 For example, you have let's say you have a string, very large string. 166 00:10:08,570 --> 00:10:12,380 So you have to give from where to where you have to go from here to here. 167 00:10:12,390 --> 00:10:15,920 You have to reverse or from starting to at the end. 168 00:10:15,950 --> 00:10:20,140 OK, so I want to reverse my hole that I want to reverse my whole vector. 169 00:10:20,360 --> 00:10:26,510 So vidauban mean the starting point without end means the ending point shaft reversing our logic and 170 00:10:26,510 --> 00:10:28,370 our colistin, I will likely return. 171 00:10:29,510 --> 00:10:31,910 OK, now one interesting thing. 172 00:10:32,180 --> 00:10:39,140 See, the level of discussion is basically easy one and the previous quotient at that level was medium. 173 00:10:39,170 --> 00:10:40,900 OK, so this is like very funny. 174 00:10:41,600 --> 00:10:42,670 So our work is done. 175 00:10:42,680 --> 00:10:45,770 I have to just write this line and now let us submit our good. 176 00:10:48,450 --> 00:10:50,780 OK, so our court is working now. 177 00:10:51,510 --> 00:10:56,390 So this is basically execution and this is basically medium question. 178 00:10:56,400 --> 00:10:58,150 So like this is like really funny. 179 00:10:58,180 --> 00:11:01,190 OK, so if you have any doubt, you can ask me. 180 00:11:01,200 --> 00:11:01,980 OK, thank you.