1
00:00:01,440 --> 00:00:02,100
Hi, everyone.

2
00:00:02,130 --> 00:00:06,240
So today we are going to solve this question, check if a binary tree.

3
00:00:07,290 --> 00:00:08,550
Is a birthday or not?

4
00:00:09,330 --> 00:00:14,680
OK, so first of all, what is so BSU stands for by history?

5
00:00:14,970 --> 00:00:19,190
OK, and what is the property of a beast so invested?

6
00:00:19,190 --> 00:00:21,620
The properties of Vesti are very simple.

7
00:00:21,930 --> 00:00:24,060
So suppose you have this root node.

8
00:00:25,490 --> 00:00:35,090
OK, so if will go left, then all the nodes in the left hand side, so their data will be less than

9
00:00:35,120 --> 00:00:36,440
the data of the root node.

10
00:00:39,410 --> 00:00:43,370
Similarly, if you will go in the right hand side of the root node, then.

11
00:00:44,490 --> 00:00:46,050
The data of all the nodes.

12
00:00:47,100 --> 00:00:49,320
Will be greater than the data through a..

13
00:00:49,770 --> 00:00:52,680
OK, so this is very simple property of obesity.

14
00:00:53,360 --> 00:00:53,760
OK.

15
00:00:53,940 --> 00:00:56,030
And so what is the input?

16
00:00:56,060 --> 00:01:02,160
So the input given is basically a binary tree and we have to return a boolean value.

17
00:01:02,670 --> 00:01:07,200
OK, whether that by the tree, if the banditry is about, I will return.

18
00:01:07,200 --> 00:01:10,770
True, if the binary trees not vestey then I will return false.

19
00:01:11,520 --> 00:01:13,920
OK, so how can I solve this question.

20
00:01:14,990 --> 00:01:17,280
So there are two ways to solve this question.

21
00:01:17,500 --> 00:01:19,140
OK, so the first we.

22
00:01:20,760 --> 00:01:27,000
So the first race, basically, we know that in order traversal of a BSD sorted, OK, this is the property

23
00:01:27,000 --> 00:01:31,920
for Besty, the in order traversal of best is sorted.

24
00:01:32,400 --> 00:01:33,330
So very simple.

25
00:01:33,850 --> 00:01:36,260
OK, so consider this example.

26
00:01:36,300 --> 00:01:37,340
This is a binary tree.

27
00:01:37,590 --> 00:01:39,150
So what is in order traversal?

28
00:01:39,150 --> 00:01:46,080
So in order to resources, first you visit the left subtree, then the current node data and then the

29
00:01:46,080 --> 00:01:46,930
right subtree.

30
00:01:46,980 --> 00:01:54,270
OK, so Ali, are now let us consider this binary tree and now let us perform it's traversal.

31
00:01:55,260 --> 00:01:56,870
So what will be the traversal.

32
00:01:56,880 --> 00:01:58,110
So suppose this is the.

33
00:01:58,150 --> 00:01:59,250
So this is the root node.

34
00:02:00,950 --> 00:02:06,160
So terror cell will be one, then two, then three, then four and then five.

35
00:02:06,220 --> 00:02:09,860
OK, now you can check this is basically sorted.

36
00:02:11,039 --> 00:02:12,070
One, two, three, four, five.

37
00:02:12,090 --> 00:02:18,600
This is sorted so I can see that this binary tree is basically Vesti.

38
00:02:18,670 --> 00:02:27,740
OK, so this binary tree is besty because it's traversal is sorted and only BSD there was in reversal

39
00:02:27,750 --> 00:02:28,210
sorted.

40
00:02:28,620 --> 00:02:31,860
Now let us perform the reversal of this bindery.

41
00:02:32,080 --> 00:02:37,770
OK, so it will be one, then five, then three, then four and then six.

42
00:02:37,990 --> 00:02:42,100
OK, so basically this is not sorted since this is not sorted.

43
00:02:42,270 --> 00:02:44,860
So this by military is not besty.

44
00:02:44,910 --> 00:02:46,920
OK, so this is not Vesty.

45
00:02:47,820 --> 00:02:50,050
You can see season or number four.

46
00:02:50,190 --> 00:02:56,640
OK, so this normal four qualifies for bisdee, but this note number five does not qualify because in

47
00:02:56,640 --> 00:02:59,280
the left hand side you have one perfectly fine.

48
00:02:59,490 --> 00:03:05,140
But in the right hand side you have this node four and four is basically less than five.

49
00:03:05,340 --> 00:03:07,860
So this binary is not Vesti.

50
00:03:09,030 --> 00:03:15,710
OK, so the first way to solve this question, what we will do, so we will perform the travesty of

51
00:03:15,720 --> 00:03:18,930
the best and let's say we will store the result in energy.

52
00:03:19,800 --> 00:03:27,500
OK, so what we will do, we will restore the traversal of the given by Nutri in an area.

53
00:03:28,080 --> 00:03:32,640
So this area will contain the reversal of the binary tree of the given by Nutri.

54
00:03:32,790 --> 00:03:36,150
Then I will check whether this area is sorted area or not.

55
00:03:36,960 --> 00:03:41,840
If this is sorted, then I will return to the given by is best.

56
00:03:42,240 --> 00:03:45,360
If this area is not sorted, then I will return false.

57
00:03:45,390 --> 00:03:49,290
So this binary is not the best if that is not sorted.

58
00:03:49,810 --> 00:03:51,490
OK, so very simple approach.

59
00:03:51,780 --> 00:03:54,750
So what would be the time and the space complexity of this approach?

60
00:03:55,000 --> 00:03:58,500
So time complexity is basically so we have to go through each and every node.

61
00:03:58,740 --> 00:04:04,860
So suppose there are end nodes so time complexity will be big off and and what is the space complexity.

62
00:04:04,890 --> 00:04:08,640
So it will be big off and OK, we have to store and node.

63
00:04:10,920 --> 00:04:15,060
So what is and is basically the total number of nodes present in the binary tree?

64
00:04:15,480 --> 00:04:19,290
OK, so this is the time in this space complexity of using this approach.

65
00:04:20,360 --> 00:04:27,200
Now, one thing that I want to share is basically so what we can do here is so there's no need to create

66
00:04:27,470 --> 00:04:27,730
this.

67
00:04:28,230 --> 00:04:30,150
OK, there is no need to create this idea.

68
00:04:30,170 --> 00:04:35,620
So what we will do so we will take two pointer, previous pointer and the current pointer.

69
00:04:35,900 --> 00:04:38,240
And while we are doing the traversal.

70
00:04:39,680 --> 00:04:47,540
While we are performing the traversal we will check, previous data should be less than the data current

71
00:04:47,540 --> 00:04:47,930
data.

72
00:04:47,990 --> 00:04:55,280
OK, so if this condition is always valid, then basically the error is sorted, then sorted so you

73
00:04:55,280 --> 00:04:57,570
can return bisdee the given by degrees.

74
00:04:58,340 --> 00:05:07,250
And if at any point this condition fails, basically previous data is greater than current data, then

75
00:05:07,250 --> 00:05:08,540
you can return that.

76
00:05:08,540 --> 00:05:13,320
The given by Nutri is not about because it's in at least not sorted.

77
00:05:13,700 --> 00:05:18,230
OK, so here, how do we check whether it is sorted or not?

78
00:05:18,260 --> 00:05:25,460
Basically we take two pointers, so previous and current pointer and we will check that previous data

79
00:05:25,460 --> 00:05:28,260
should be less than the date of the current pointer.

80
00:05:28,280 --> 00:05:29,870
OK, so this weekend can.

81
00:05:30,690 --> 00:05:36,530
So instead of creating this area when we are performing the traversal, we can check this condition

82
00:05:36,530 --> 00:05:37,380
for every node.

83
00:05:37,820 --> 00:05:44,360
OK, so in this way the time complexity is still big often, but the space complexity will be Goffman

84
00:05:44,600 --> 00:05:46,190
because there is no need to create.

85
00:05:47,500 --> 00:05:48,100
This Eddie.

86
00:05:48,130 --> 00:05:49,900
OK, there's no need to create this, Eddie.

87
00:05:50,770 --> 00:05:53,850
Now, let's discuss the second way of solving this question, OK?

88
00:05:55,330 --> 00:06:03,760
So let us take this example, four to five, one three, so I have this for two, then five and I have

89
00:06:03,760 --> 00:06:05,290
one and then I have three.

90
00:06:05,350 --> 00:06:08,990
OK, so let's discuss the second way of solving this question.

91
00:06:10,480 --> 00:06:15,850
So what we're going to do here is so basically each node has some constraint.

92
00:06:15,920 --> 00:06:19,730
OK, so each node has some constraint and what is that constraint?

93
00:06:20,500 --> 00:06:22,990
So let's discuss that constraint for the root node.

94
00:06:23,680 --> 00:06:29,110
So this value, this value can be from minus infinity to plus infinity.

95
00:06:29,120 --> 00:06:31,210
It can be anything, OK?

96
00:06:31,390 --> 00:06:35,500
Root data can be anything but if it will go in the left hand side.

97
00:06:37,010 --> 00:06:43,970
Suppose the input is basically about, OK, so suppose I am discussing the property of about OK, I

98
00:06:44,000 --> 00:06:45,260
am discussing the property, everybody.

99
00:06:45,650 --> 00:06:47,510
So if it will go in the left hand side.

100
00:06:48,810 --> 00:06:52,530
What can be the data of this value, what can be the data for this?

101
00:06:52,530 --> 00:06:53,430
Not so.

102
00:06:53,430 --> 00:07:00,600
The minimum value can be minus infinity, but the maximum value can be four by four, because four is

103
00:07:00,600 --> 00:07:01,320
the root node.

104
00:07:02,300 --> 00:07:08,450
OK, so the value of this node will lie between minus infinity to four, because this is the property

105
00:07:08,450 --> 00:07:11,090
of the best that if it will go in the left hand side.

106
00:07:12,500 --> 00:07:18,080
So the left the debate of the left node will always be smaller than the route node data.

107
00:07:19,070 --> 00:07:23,720
OK, so for this node, this is the constraint.

108
00:07:24,230 --> 00:07:27,200
The value will lie between minus infinity for OK.

109
00:07:27,410 --> 00:07:29,270
Now suppose you again go left.

110
00:07:30,420 --> 00:07:31,680
So for Naude, No.

111
00:07:31,740 --> 00:07:32,140
One.

112
00:07:32,160 --> 00:07:37,860
So basically for disaccord, the minimum value will be minus infinity, but the maximum value can be

113
00:07:37,860 --> 00:07:38,490
two only.

114
00:07:38,710 --> 00:07:43,170
OK, the maximum value will be two if you will go in the right hand side.

115
00:07:44,300 --> 00:07:48,080
So the minimum value will be to and the maximum value will be for.

116
00:07:48,260 --> 00:07:51,570
OK, so this for the maximum value will be for.

117
00:07:51,950 --> 00:07:54,350
So the only possible in this three.

118
00:07:55,410 --> 00:07:57,120
Now, if you were going the right hand side.

119
00:07:58,250 --> 00:08:02,690
So basically, it's minimum wage level before and it's maximum value will be infinity.

120
00:08:03,930 --> 00:08:04,950
OK, so.

121
00:08:06,120 --> 00:08:15,510
Each node has constrained OK, each node data, each node data is bounded by a constraint that its maximum

122
00:08:15,510 --> 00:08:19,590
value will be, it will lie between the minimum and the maximum value.

123
00:08:19,590 --> 00:08:23,340
Each data will lie between a certain minimum and the maximum value.

124
00:08:24,210 --> 00:08:26,280
OK, let us take one more example.

125
00:08:26,280 --> 00:08:33,370
So suppose I have five then let's say I have this X and here I have Y.

126
00:08:33,419 --> 00:08:38,789
OK, so here I have Z and let's say here I have and here I have B.

127
00:08:39,010 --> 00:08:40,320
OK, so.

128
00:08:41,419 --> 00:08:44,700
This value can be from minus invader infinity.

129
00:08:45,410 --> 00:08:51,860
OK, so its value, so the value will be minus infinity and the maximum value will be five.

130
00:08:52,810 --> 00:08:57,550
If you will go again in the left hand side, the minimum values still minus infinity, but the maximum

131
00:08:57,550 --> 00:08:58,350
value is X.

132
00:08:59,020 --> 00:09:00,430
OK, now for Y.

133
00:09:01,360 --> 00:09:02,660
So what can be the values of.

134
00:09:02,890 --> 00:09:07,390
So basically the minimum value will be five and the maximum value will be infinity.

135
00:09:08,550 --> 00:09:14,450
For this note, the minimum, if you are going in the left hand side, so basically the minimum value

136
00:09:14,490 --> 00:09:15,730
will be five.

137
00:09:15,780 --> 00:09:23,040
OK, so this five, the minimum value will be five and the maximum value will be by OK, if you are

138
00:09:23,040 --> 00:09:24,330
going in the right hand side.

139
00:09:24,600 --> 00:09:28,410
So the minimum value will be way and the maximum value will be infinity.

140
00:09:29,250 --> 00:09:31,180
OK, so what is the second approach.

141
00:09:31,560 --> 00:09:33,450
So second approach says.

142
00:09:34,630 --> 00:09:38,860
Basically, you check the constraint of every node.

143
00:09:39,520 --> 00:09:45,340
OK, I will check the constraint for every node if the constraint is valid, if all the nodes.

144
00:09:46,550 --> 00:09:49,740
Are having this constraint then it is about race.

145
00:09:49,760 --> 00:09:50,870
It is not about.

146
00:09:52,050 --> 00:10:00,470
OK, I'm repeating myself, the second approach will go to each and every node, OK, approaches, go

147
00:10:00,480 --> 00:10:03,570
to each node and check their constraint.

148
00:10:03,600 --> 00:10:05,110
OK, what is the constraint?

149
00:10:05,370 --> 00:10:07,560
So this is the constraint of data constraint.

150
00:10:07,740 --> 00:10:11,630
If every node follows the data constraint, OK, it is very simple.

151
00:10:12,000 --> 00:10:16,410
If every node follows its data constraint, then it is a BSD.

152
00:10:16,440 --> 00:10:20,180
Otherwise it is not OK if every in order for the constraint.

153
00:10:20,970 --> 00:10:25,500
So if it is true then the given binit it is best raise.

154
00:10:25,620 --> 00:10:28,200
The given by Nutri is not ok.

155
00:10:30,920 --> 00:10:34,430
So I think this approach, number one, is very easy to implement.

156
00:10:34,610 --> 00:10:42,260
OK, so what we are doing, we will just perform the traversal and we will take two point up us point

157
00:10:42,260 --> 00:10:43,000
and point out.

158
00:10:43,010 --> 00:10:45,030
And we will we will have to check this condition.

159
00:10:45,050 --> 00:10:47,810
OK, then we can return whether the.

160
00:10:48,780 --> 00:10:53,470
Guarantees BSG or not, but the second approach, I think, is a little bit difficult.

161
00:10:53,790 --> 00:10:55,860
So let us implement the second approach.

162
00:10:56,740 --> 00:11:02,270
OK, so what we will do is first let us take this example.

163
00:11:02,280 --> 00:11:03,840
Also five 146.

164
00:11:04,530 --> 00:11:08,290
OK, now let us check whether this five 146.

165
00:11:09,150 --> 00:11:14,040
So I have five one four and then I have three and six.

166
00:11:15,060 --> 00:11:20,080
OK, so its value can be from minus infinity to infinity and its value is five.

167
00:11:20,100 --> 00:11:21,270
So this note is correct.

168
00:11:22,340 --> 00:11:30,290
If I'm going on the left hand side, so its value will be from minus infinity to five and one lies between

169
00:11:30,290 --> 00:11:30,590
this.

170
00:11:30,740 --> 00:11:32,640
OK, so this node is also correct.

171
00:11:32,950 --> 00:11:34,640
Now check this node for.

172
00:11:35,550 --> 00:11:42,480
So it's minimum value is basically five and it's maximum value is basically infinity, and four does

173
00:11:42,480 --> 00:11:44,370
not lie between five and infinity.

174
00:11:44,820 --> 00:11:48,490
OK, so that means this tree is not a beast.

175
00:11:49,080 --> 00:11:54,030
OK, this tree is not beast because fall does not lie between five and infinity.

176
00:11:55,580 --> 00:11:57,420
OK, so what will be our approach?

177
00:11:58,070 --> 00:12:02,330
So we will take the help of regulation, we are implementing second approach.

178
00:12:03,080 --> 00:12:05,540
OK, so we will take the help of regulation.

179
00:12:05,550 --> 00:12:07,250
So this is the left subtree.

180
00:12:07,910 --> 00:12:09,770
This is the right subtree.

181
00:12:11,990 --> 00:12:17,570
OK, so what we will do, so I will call the functionality of the neural function is is bisdee.

182
00:12:18,880 --> 00:12:24,580
So I will call the function on the left hand side, the left hand side should be left subtree should

183
00:12:24,580 --> 00:12:25,150
be bisdee.

184
00:12:26,370 --> 00:12:26,750
Right.

185
00:12:26,770 --> 00:12:29,580
Somebody should be best and for.

186
00:12:30,120 --> 00:12:34,360
I will check whether the days lag between minus infinity to infinity.

187
00:12:34,890 --> 00:12:35,580
Very simple.

188
00:12:35,820 --> 00:12:42,900
OK, so your condition if the left to is a body, if the right is a beast, and if the narrator lies

189
00:12:42,900 --> 00:12:49,620
between minus infinity to infinity, then I will return to that the given prize bastia that I will return

190
00:12:49,620 --> 00:12:50,010
false.

191
00:12:50,220 --> 00:12:52,210
OK, so I hope you understand the logic.

192
00:12:52,230 --> 00:12:54,030
Now let us write the code, ok.

193
00:12:55,520 --> 00:12:59,990
So basically, this is a legitimate question validated by necessity.

194
00:13:00,050 --> 00:13:03,070
OK, so now let us write the code.

195
00:13:03,230 --> 00:13:04,490
OK, so one thing.

196
00:13:05,330 --> 00:13:11,600
So I told you that the value of fruit will basically lie between minus infinity and basically plus infinity.

197
00:13:11,810 --> 00:13:14,550
So let us define what R minus and plus infinity.

198
00:13:14,570 --> 00:13:18,770
OK, what what is the meaning of minus infinity and what is the meaning of plus infinity.

199
00:13:19,220 --> 00:13:24,650
OK, so basically in C++ integer itself, 32 bits.

200
00:13:26,580 --> 00:13:33,350
OK, so that means the maximum value of integer can be to the power 31 and the minimum value of integer

201
00:13:33,350 --> 00:13:36,050
can be minus two to the power to be one minus one.

202
00:13:36,110 --> 00:13:41,360
OK, so this is basically let's call it it is nearly equal to the power nine.

203
00:13:41,570 --> 00:13:45,950
And similarly this is also nearly equal to minus 10 to the power nine.

204
00:13:46,190 --> 00:13:49,080
OK, so by plus infinity.

205
00:13:49,130 --> 00:13:51,460
OK, so this plus infinity.

206
00:13:51,800 --> 00:13:52,830
So it should be good.

207
00:13:52,850 --> 00:13:58,660
Then at about nine let's call it ten to the power 10 and similarly this minus infinity.

208
00:13:58,940 --> 00:14:03,490
So this should be listin ten to the power minus the power line.

209
00:14:03,740 --> 00:14:06,380
So let's call it minus 20 the power then.

210
00:14:07,220 --> 00:14:08,990
OK, so these are distributed.

211
00:14:10,090 --> 00:14:11,350
So they are inclusive.

212
00:14:11,380 --> 00:14:18,430
OK, so for root, root can take the valley of basically minus 10 to the power line and it can take

213
00:14:18,430 --> 00:14:20,500
the valley of the power line.

214
00:14:20,560 --> 00:14:22,960
OK, so now let's ride the gold.

215
00:14:24,670 --> 00:14:26,630
So this is basically a little problem.

216
00:14:26,650 --> 00:14:31,690
OK, so their function is bull and then it's basically a root.

217
00:14:31,880 --> 00:14:39,160
OK, so let us create a helper function so that the helper function will be able.

218
00:14:40,640 --> 00:14:42,230
So what this function will take?

219
00:14:43,240 --> 00:14:44,530
This function will take.

220
00:14:45,870 --> 00:14:46,560
Root node.

221
00:14:47,920 --> 00:14:50,260
And the minimum and the maximum value of the loot.

222
00:14:50,650 --> 00:14:54,700
OK, so here the what is the minimum?

223
00:14:54,700 --> 00:14:55,230
The maximum.

224
00:14:56,050 --> 00:15:01,760
So the normal life between minus infinity to plus infinity and both are inclusive.

225
00:15:01,780 --> 00:15:09,220
OK, so minus infinity is basically minus 10 to the power nine and plus introduced into the lower nine.

226
00:15:09,260 --> 00:15:11,910
OK, so what I will pass.

227
00:15:11,920 --> 00:15:13,000
So I am passing.

228
00:15:13,780 --> 00:15:14,880
These are inclusive.

229
00:15:15,130 --> 00:15:22,060
So that means if I want to exclude this I can write minus 10 to the power, Ten Commandments, the power

230
00:15:22,060 --> 00:15:22,350
then.

231
00:15:22,750 --> 00:15:25,870
But this number is big so it cannot be stored in integer.

232
00:15:25,870 --> 00:15:27,220
So I will store it long.

233
00:15:27,220 --> 00:15:27,550
Long.

234
00:15:28,450 --> 00:15:33,880
OK, this number is big, so I cannot turn it in, so who have to store this number in a long, long

235
00:15:33,880 --> 00:15:34,930
and similarly for this?

236
00:15:35,180 --> 00:15:37,060
OK, so I have to take long, long.

237
00:15:38,860 --> 00:15:45,820
So this route will lie between two variables, minimum and the maximum, so the minimum value is basically

238
00:15:46,030 --> 00:15:51,420
you can pass the default argument, so then minimum will be minus 10 to the power 10.

239
00:15:51,430 --> 00:15:56,110
OK, so 10 zeroes, one, two, three, four, five, six, seven, eight, nine, 10.

240
00:15:56,660 --> 00:15:57,100
OK.

241
00:15:58,330 --> 00:15:59,200
And similarly.

242
00:16:00,460 --> 00:16:06,480
The maximum value of fruit can be what is the maximum value of fruit, so it can be 10 to the Barberton.

243
00:16:06,530 --> 00:16:12,100
OK, it will be tendered about so one, two, three, four, five, six, seven, eight, nine, 10.

244
00:16:12,130 --> 00:16:13,190
And the rules, basically.

245
00:16:13,780 --> 00:16:14,590
So one thing.

246
00:16:16,270 --> 00:16:17,740
So here I am digging.

247
00:16:18,920 --> 00:16:24,240
Down to the bottom, you can also take 10 to the power, 11 or 10 to the power to end and so on, but

248
00:16:24,460 --> 00:16:26,910
the power then is will do our work.

249
00:16:26,930 --> 00:16:28,970
OK, so this is more than enough.

250
00:16:28,970 --> 00:16:29,910
It will do our job.

251
00:16:29,970 --> 00:16:33,800
And similarly, ministered to the power then will do our work.

252
00:16:33,860 --> 00:16:37,330
OK, so now what we have to do.

253
00:16:37,340 --> 00:16:38,620
So let us ride the bike.

254
00:16:38,840 --> 00:16:39,940
So what is the best case.

255
00:16:40,760 --> 00:16:47,460
So if through dismal IFPRI does not exist, then I can say that given by Nutri is basically biased.

256
00:16:47,510 --> 00:16:54,410
So I will return to OK now if we have to do first, let us check whether the left is biased or not.

257
00:16:54,650 --> 00:17:00,710
So let us call the helper function so I will pass the left subtree.

258
00:17:01,190 --> 00:17:02,480
So rude and left.

259
00:17:03,450 --> 00:17:09,569
Now, what is the minimum value, what is the minimum value for the left subtree, so it will be same

260
00:17:09,569 --> 00:17:11,130
as minimum value for the root.

261
00:17:12,349 --> 00:17:13,880
And what is the maximum value?

262
00:17:14,940 --> 00:17:19,050
So basically, the maximum value will be route data.

263
00:17:19,079 --> 00:17:21,540
OK, so Rotaru value.

264
00:17:24,150 --> 00:17:25,170
OK, so one thing.

265
00:17:26,550 --> 00:17:28,410
So if you have a binary tree.

266
00:17:29,940 --> 00:17:37,050
This is one, and this is one, so basically this Binit is not bisdee, OK, this is not Vesti because

267
00:17:37,920 --> 00:17:43,900
its range is between minus and to infinity, but its range is between minus infinity to one.

268
00:17:43,950 --> 00:17:47,760
OK, so basically this one is this one, OK?

269
00:17:47,940 --> 00:17:49,330
And this one is basically.

270
00:17:49,350 --> 00:17:53,960
So this is this type of this type of record means this one is not included.

271
00:17:54,000 --> 00:17:56,230
OK, this is not included.

272
00:17:56,250 --> 00:17:57,450
So this is excluded.

273
00:18:00,700 --> 00:18:07,200
So since this one equals close to this one, so that means this is not about OK, this is not about

274
00:18:07,300 --> 00:18:13,820
because strictly left values should be less than root values.

275
00:18:15,520 --> 00:18:18,620
OK, this is not less than articles two.

276
00:18:18,650 --> 00:18:20,350
This is strictly Leston, OK?

277
00:18:21,380 --> 00:18:26,840
So that's why if the input is this now put this this is not about OK.

278
00:18:28,710 --> 00:18:32,830
And similarly, let us check whether the right surprise you or not.

279
00:18:33,510 --> 00:18:35,250
So let us call the helper function.

280
00:18:36,640 --> 00:18:38,860
I will bust the right subtree.

281
00:18:40,860 --> 00:18:43,370
Now, what is the minimum wage, so minimum values?

282
00:18:43,410 --> 00:18:43,870
Nothing.

283
00:18:43,920 --> 00:18:44,400
It is.

284
00:18:45,780 --> 00:18:46,500
Rude value.

285
00:18:46,530 --> 00:18:46,860
OK.

286
00:18:47,890 --> 00:18:52,930
And what is the maximum value, so the maximum value is plus infinity, basically this number 10 to

287
00:18:52,930 --> 00:18:53,260
the power.

288
00:18:53,630 --> 00:18:53,980
OK.

289
00:18:55,140 --> 00:18:59,280
Now, our trees vista if and only if left some trees.

290
00:18:59,730 --> 00:19:07,710
So if left and right surprised Besty and the value of fruit.

291
00:19:10,860 --> 00:19:12,540
And the root value.

292
00:19:14,140 --> 00:19:18,400
Basically, it lies between plus infinity and minus infinity.

293
00:19:18,430 --> 00:19:19,540
OK, so this condition.

294
00:19:22,910 --> 00:19:25,310
So the value of fruit.

295
00:19:27,210 --> 00:19:30,420
So it should be basically greater than the minimum value.

296
00:19:31,410 --> 00:19:32,670
And it should be.

297
00:19:35,530 --> 00:19:40,720
Less than the maximum value, if these four conditions are true, then I will return to.

298
00:19:42,370 --> 00:19:44,470
In the elford, I will return false.

299
00:19:46,420 --> 00:19:53,830
OK, so let's call the helper function from Dimin, so return helper, when I will pass, I will pass

300
00:19:53,830 --> 00:19:54,360
on the road.

301
00:19:54,430 --> 00:19:56,590
OK, so these are default arguments.

302
00:19:57,800 --> 00:20:01,550
So let us not our call, and then we will try to submit our code, OK?

303
00:20:05,330 --> 00:20:07,220
OK, so now let's meet our good.

304
00:20:09,930 --> 00:20:11,800
OK, so our court is working fine.

305
00:20:11,820 --> 00:20:14,280
OK, now let's see what we are doing here.

306
00:20:16,460 --> 00:20:19,140
OK, so this helper function is doing all the work.

307
00:20:19,160 --> 00:20:21,350
OK, so this is taking root.

308
00:20:21,650 --> 00:20:26,720
So this is taking the minimum value of the root, which is which I'm calling minus infinity.

309
00:20:26,720 --> 00:20:32,600
And it is calling the plus it is calling the maximal of the root, which which I'm calling is plus infinity.

310
00:20:32,630 --> 00:20:35,150
OK, so four root node.

311
00:20:36,540 --> 00:20:41,340
The value is between minus infinity open bracket and plus infinity open bracket.

312
00:20:41,380 --> 00:20:47,460
OK, so the value of fruit can be close to two to the power to divine, which is the maximum value for

313
00:20:47,460 --> 00:20:48,120
an integer.

314
00:20:48,180 --> 00:20:52,160
OK, so and this value is equal to around 10 to the power nine.

315
00:20:52,410 --> 00:20:56,320
So to the power nine is basically included in this.

316
00:20:56,340 --> 00:21:02,730
OK, so that is about nine will be included from minus 10 to the power 10 to 10 to the power then.

317
00:21:02,820 --> 00:21:05,490
OK, so no problem then.

318
00:21:05,490 --> 00:21:08,220
If the root is nil, obviously we can directly return.

319
00:21:08,220 --> 00:21:10,440
True, because the given binary will be bisdee.

320
00:21:11,130 --> 00:21:15,990
Now I'm calling on the left subtree, then I am calling on the right subtree and then I am checking

321
00:21:15,990 --> 00:21:16,590
the condition.

322
00:21:16,870 --> 00:21:20,330
So if the left is the right, surprise Vesti.

323
00:21:20,520 --> 00:21:23,700
And now here I am checking the constraint on the root node.

324
00:21:23,880 --> 00:21:29,460
OK, so if the value of root node is greater than the minimum value and the value of node is less than

325
00:21:29,460 --> 00:21:33,270
the maximum value, then return to azn false.

326
00:21:33,330 --> 00:21:34,660
OK, so very simple.

327
00:21:34,860 --> 00:21:36,780
What is the time complexity of this approach?

328
00:21:37,050 --> 00:21:39,310
So basically we are going through each and every node.

329
00:21:39,330 --> 00:21:44,850
So if data and NATO time complexity is big off and now what does this space complexity.

330
00:21:45,510 --> 00:21:50,670
So the space complexity you can say or Draffin if you are considering the cost.

331
00:21:50,830 --> 00:21:52,410
So basically we are using recursion.

332
00:21:52,410 --> 00:21:54,570
So the recursion we have a call stack.

333
00:21:54,930 --> 00:22:00,900
So if you will consider this memory, if you will consider the constant memory, then it is ultrafine.

334
00:22:01,050 --> 00:22:02,790
Otherwise it is order of one.

335
00:22:03,730 --> 00:22:04,150
OK.

336
00:22:05,210 --> 00:22:10,400
Now, if you didn't like this approach, we also discussed about the first approach, what we can do.

337
00:22:10,670 --> 00:22:18,320
We will simply do traversal need traversal and we will store the sell output in an eddy.

338
00:22:19,630 --> 00:22:26,740
And if this stays sorted, then the then basically the binary trees, BSG either remains or does not.

339
00:22:27,190 --> 00:22:29,190
OK, so this is very simple to implement.

340
00:22:29,200 --> 00:22:30,610
It is very easy to implement.

341
00:22:30,850 --> 00:22:32,200
It can implement it yourself.

342
00:22:32,230 --> 00:22:37,840
OK, so in this case, also the time complexity we have already discussed Magoffin and the space complexity

343
00:22:37,840 --> 00:22:38,440
is also big.

344
00:22:38,440 --> 00:22:40,300
Often if you are creating the very.

345
00:22:41,450 --> 00:22:45,340
But if you will write code in a good matter, then there is no need to create this area.

346
00:22:45,500 --> 00:22:51,260
You can take two pointer, three pointer and current pointer and you can easily compare the date of

347
00:22:51,260 --> 00:22:57,340
these two points and you will be able to solve this problem in open space using the Internet.

348
00:22:57,860 --> 00:22:58,190
OK.

349
00:23:00,300 --> 00:23:02,790
So if you have any doubt in this question, you can ask me.

350
00:23:02,820 --> 00:23:03,600
OK, thank you.

