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.

