1
00:00:00,630 --> 00:00:01,590
Welcome back.

2
00:00:01,590 --> 00:00:07,230
Let's now go ahead and write the function to check whether the binary tree which is given to us is a

3
00:00:07,230 --> 00:00:09,300
valid binary search tree or not.

4
00:00:09,300 --> 00:00:12,210
So over here we have the class node.

5
00:00:12,210 --> 00:00:14,970
And then we have the binary tree class over here.

6
00:00:14,970 --> 00:00:18,660
And then we have the insert function, which we have discussed in a previous video.

7
00:00:18,660 --> 00:00:24,840
And using this instance method I have created a binary tree over here and these values have been inserted.

8
00:00:24,840 --> 00:00:30,840
So we will now go ahead and write the function to check whether this binary tree is a valid binary search

9
00:00:30,840 --> 00:00:31,680
tree or not.

10
00:00:31,680 --> 00:00:33,450
So let's go ahead and write the function.

11
00:00:33,450 --> 00:00:35,010
So let's have a comment over here.

12
00:00:35,010 --> 00:00:37,530
So this is going to be the function to check.

13
00:00:38,390 --> 00:00:43,160
Whether the tree is a valid binary search tree.

14
00:00:43,160 --> 00:00:45,020
So let's call this function.

15
00:00:45,140 --> 00:00:47,360
Check if.

16
00:00:47,760 --> 00:00:48,540
Valid.

17
00:00:49,330 --> 00:00:50,080
BSD.

18
00:00:50,680 --> 00:00:54,880
Now this function is going to take in the root of the binary tree.

19
00:00:54,880 --> 00:00:56,560
So it's going to take in the root.

20
00:00:56,770 --> 00:01:02,440
And then now we're going to implement this as a recursive function as a recursive solution.

21
00:01:02,440 --> 00:01:08,260
So over here we're just going to return what we get back from a helper function which will check whether

22
00:01:08,260 --> 00:01:14,350
that the binary search tree with that particular node where we are currently at is a binary search tree

23
00:01:14,350 --> 00:01:14,860
or not.

24
00:01:14,860 --> 00:01:16,930
So let's now see how we implement this.

25
00:01:16,930 --> 00:01:18,610
And it will become more clear.

26
00:01:18,610 --> 00:01:21,760
Now this helper function is going to take in the node.

27
00:01:21,760 --> 00:01:23,500
So that's the root over here.

28
00:01:23,500 --> 00:01:27,250
And then the initial bounds are minus infinity.

29
00:01:29,260 --> 00:01:30,610
And infinity.

30
00:01:31,620 --> 00:01:33,720
So these are the bounds initially.

31
00:01:33,720 --> 00:01:36,690
So we have seen that at the root we can have any value.

32
00:01:36,690 --> 00:01:39,390
And still the binary search tree is going to be valid.

33
00:01:39,420 --> 00:01:42,660
Now let's go ahead and write the helper function.

34
00:01:43,770 --> 00:01:45,870
So we have const helper.

35
00:01:48,610 --> 00:01:55,510
And this function is going to take in the node and the minimum value and the maximum value.

36
00:01:57,860 --> 00:01:58,460
All right.

37
00:01:58,460 --> 00:02:04,130
Now, once inside the helper function, first we will just check if the node is equal to null.

38
00:02:04,130 --> 00:02:06,440
So if the node is equal to null.

39
00:02:08,020 --> 00:02:09,460
Then we will just return.

40
00:02:09,460 --> 00:02:10,030
True.

41
00:02:11,720 --> 00:02:12,050
All right.

42
00:02:12,050 --> 00:02:15,680
So we know that because we've seen also in the previous video in the test case.

43
00:02:15,680 --> 00:02:20,030
Also, if the binary search tree is just a null tree, we will just return true.

44
00:02:20,030 --> 00:02:25,430
And even in recursive calls, when we reach a level where the left or the right is just null, we will

45
00:02:25,430 --> 00:02:26,480
just return true.

46
00:02:26,480 --> 00:02:28,280
So that's why this is our base case.

47
00:02:28,280 --> 00:02:30,260
So let's just write a comment over here.

48
00:02:30,260 --> 00:02:32,090
So this is the base case.

49
00:02:32,830 --> 00:02:33,850
Now let's proceed.

50
00:02:33,850 --> 00:02:38,470
If this is not the case, then we are going to take the value of the node.

51
00:02:38,470 --> 00:02:42,970
So let's say let value is equal to node dot value.

52
00:02:44,100 --> 00:02:47,940
And then we're going to check whether the value is between the bounds.

53
00:02:47,940 --> 00:02:50,310
So we have the min and max bound over here.

54
00:02:50,340 --> 00:02:56,340
Now if it is not within the bounds then we know that it's not a valid binary search tree and we can

55
00:02:56,340 --> 00:02:57,630
just return false.

56
00:02:57,630 --> 00:02:58,710
So let's check that.

57
00:02:58,710 --> 00:02:59,490
So if.

58
00:03:00,200 --> 00:03:07,700
Value is less than equal to the minimum value or if value.

59
00:03:08,660 --> 00:03:11,720
Is greater than or equal to the maximum value.

60
00:03:11,720 --> 00:03:17,690
So if either of these is true, then we know that the value is not in between min and max, right.

61
00:03:17,690 --> 00:03:24,200
Because we know that ideally the required condition is that min should be less than value and that should

62
00:03:24,200 --> 00:03:25,340
be less than max.

63
00:03:25,340 --> 00:03:26,660
So this is what we want.

64
00:03:26,690 --> 00:03:31,010
Now if any of these two is true then this is violated right.

65
00:03:31,010 --> 00:03:32,240
So then this is violated.

66
00:03:32,240 --> 00:03:38,450
And in that case we know that we don't have a valid binary search tree and we can just return false.

67
00:03:39,110 --> 00:03:42,110
Now if this is not the case then we proceed further.

68
00:03:42,110 --> 00:03:44,780
Now we are going to check whether it's the nodes.

69
00:03:44,780 --> 00:03:46,220
So we are at a particular node.

70
00:03:46,220 --> 00:03:52,040
So we're going to check whether the node's left subtree and right subtree.

71
00:03:55,320 --> 00:03:56,850
Is a valid BST.

72
00:03:56,850 --> 00:03:58,530
So that's what you're checking now.

73
00:03:58,710 --> 00:03:59,310
All right.

74
00:03:59,850 --> 00:04:05,190
So let's go ahead now for checking whether the left subtree is a valid subtree.

75
00:04:05,190 --> 00:04:06,360
Valid binary search tree.

76
00:04:06,360 --> 00:04:09,450
So let's have const is left BST.

77
00:04:09,480 --> 00:04:11,730
So let's have a variable is left BST.

78
00:04:11,880 --> 00:04:15,840
And this is going to call the same function the helper function recursively.

79
00:04:15,840 --> 00:04:18,630
So only we are going to pass the node dot left over here.

80
00:04:18,630 --> 00:04:23,730
So helper and the node is going to be node dot left which you are passing to the helper function.

81
00:04:23,730 --> 00:04:29,100
And then we have seen that when we go left we are going to change the maximum right.

82
00:04:29,100 --> 00:04:31,770
So when we go left we are changing the maximum.

83
00:04:31,770 --> 00:04:34,620
And when we go right we are changing the minimum.

84
00:04:34,620 --> 00:04:37,110
So that's what we have discussed in the previous video.

85
00:04:37,110 --> 00:04:41,040
So over here we are going left because we are passing node dot left.

86
00:04:41,040 --> 00:04:43,350
So when we go left we are changing the maximum.

87
00:04:43,350 --> 00:04:47,730
So we are not changing the minimum, but the maximum is going to be changed to the value.

88
00:04:47,730 --> 00:04:49,830
Now why is it that we are changing the maximum?

89
00:04:49,830 --> 00:04:55,560
Because we know that when we go left, we need something which is less than the value which is there

90
00:04:55,560 --> 00:04:56,730
at the node.

91
00:04:56,730 --> 00:04:56,940
Right?

92
00:04:56,940 --> 00:05:01,560
So that's why the maximum possible is something that is less than the current value.

93
00:05:01,560 --> 00:05:01,920
All right.

94
00:05:01,920 --> 00:05:04,260
So that's why we are changing the maximum to value.

95
00:05:04,260 --> 00:05:08,610
Now let's go ahead and also check whether the right subtree is a valid BST.

96
00:05:08,610 --> 00:05:11,940
So for this let's again have const is right.

97
00:05:12,750 --> 00:05:13,440
BSD.

98
00:05:13,440 --> 00:05:14,460
So that's a variable.

99
00:05:14,490 --> 00:05:16,650
Now this is either going to be true or false.

100
00:05:16,650 --> 00:05:21,420
And then we're going to call the helper function recursively and pass node dot right.

101
00:05:21,420 --> 00:05:26,250
And because we are going right we are going to change the minimum to value.

102
00:05:27,060 --> 00:05:29,910
And the maximum is staying as it is.

103
00:05:30,270 --> 00:05:33,390
Now each of these is going to be true or false.

104
00:05:33,390 --> 00:05:38,910
So when it returns and then we are just going to return true if both of them are true.

105
00:05:38,910 --> 00:05:44,760
So we are going to say return is left BST and and is right BST.

106
00:05:44,790 --> 00:05:47,640
So if both of them are true then we will return true.

107
00:05:47,640 --> 00:05:49,860
Otherwise we will return false.

108
00:05:49,860 --> 00:05:52,290
So this is how we have solved this question.

109
00:05:52,290 --> 00:05:56,820
You can see that because this is a recursive implementation, the number of lines of code that we have

110
00:05:56,820 --> 00:05:58,230
to write is very much less.

111
00:05:58,230 --> 00:06:04,860
Now let's go ahead and try to see whether this binary search tree is a valid binary search tree or not.

112
00:06:04,860 --> 00:06:06,030
This binary tree over here.

113
00:06:06,030 --> 00:06:10,140
Now, before we run the code, let me just draw this over here so that we can visualize it.

114
00:06:10,840 --> 00:06:11,350
All right.

115
00:06:11,350 --> 00:06:16,960
So I have just drawn the binary tree over here, which we have created using the dot insert instance

116
00:06:16,960 --> 00:06:17,440
method.

117
00:06:17,440 --> 00:06:18,640
So we have ten over here.

118
00:06:18,640 --> 00:06:20,050
Then we have five and 20.

119
00:06:20,050 --> 00:06:21,790
So that's five and 20 over here.

120
00:06:21,790 --> 00:06:23,920
Then we have three and seven.

121
00:06:23,920 --> 00:06:25,570
So three and seven is over here.

122
00:06:25,570 --> 00:06:27,100
Then we have 15 and 30.

123
00:06:27,100 --> 00:06:28,360
So 15 and 30 is over here.

124
00:06:28,360 --> 00:06:29,350
And it goes on like that.

125
00:06:29,350 --> 00:06:30,880
So we have null and four.

126
00:06:30,880 --> 00:06:33,340
So that's why this over here is null.

127
00:06:33,340 --> 00:06:35,170
And then we have four then null and null.

128
00:06:35,170 --> 00:06:38,350
So that's the left and right of this node over here which is seven.

129
00:06:38,350 --> 00:06:40,060
And then we have null and 17.

130
00:06:40,060 --> 00:06:42,730
So we have null over here this is null.

131
00:06:42,730 --> 00:06:44,050
And then this is 17.

132
00:06:44,050 --> 00:06:45,400
And then we have null and null.

133
00:06:45,400 --> 00:06:47,350
So that's the left and right for 30.

134
00:06:47,350 --> 00:06:50,500
And then we have null and null which is the left and right for four.

135
00:06:50,500 --> 00:06:52,510
And then we have null and 18.

136
00:06:52,510 --> 00:06:53,410
So that's this.

137
00:06:53,410 --> 00:06:56,590
So the left of 17 is null and the right is 18.

138
00:06:56,590 --> 00:06:58,840
So this is the binary tree which we have created.

139
00:06:58,840 --> 00:07:04,540
Now let's call the function which we have just now returned to check whether this binary tree over here

140
00:07:04,540 --> 00:07:06,760
is a valid binary search tree or not.

141
00:07:06,760 --> 00:07:09,220
Now before we run the code, what's our expectation?

142
00:07:09,220 --> 00:07:11,890
We can see that this is actually a binary search tree.

143
00:07:11,890 --> 00:07:12,160
Right?

144
00:07:12,160 --> 00:07:15,130
So everything to the left of ten is less than ten.

145
00:07:15,130 --> 00:07:17,500
Everything to the right of ten is greater than ten.

146
00:07:17,500 --> 00:07:19,510
And it's true for each of these nodes.

147
00:07:19,510 --> 00:07:19,720
Right.

148
00:07:19,720 --> 00:07:24,910
For for example, for five everything to its left is less than five, and to its right we have greater

149
00:07:24,910 --> 00:07:25,420
than five.

150
00:07:25,420 --> 00:07:31,060
And for 20, everything to the left of 20 is less than 20, and everything to the right of 20 is greater

151
00:07:31,060 --> 00:07:31,540
than 20.

152
00:07:31,540 --> 00:07:33,820
So this is actually a binary search tree.

153
00:07:33,820 --> 00:07:36,040
Binary, uh, valid binary search tree.

154
00:07:36,070 --> 00:07:38,050
Now let's go ahead and run the function.

155
00:07:38,050 --> 00:07:40,390
So let's call check if valid BST.

156
00:07:40,540 --> 00:07:42,730
So we're going to call the function.

157
00:07:42,730 --> 00:07:46,090
And we are going to pass in the root of this binary tree.

158
00:07:46,090 --> 00:07:49,660
So tree dot root is what we pass in as a parameter.

159
00:07:49,660 --> 00:07:53,860
And let's now go ahead and run the function and see what we are getting.

160
00:07:55,150 --> 00:07:55,510
Okay.

161
00:07:55,510 --> 00:07:57,010
We have an error.

162
00:07:57,010 --> 00:07:58,480
So let's just check that over here.

163
00:08:01,910 --> 00:08:03,020
Node is equal to.

164
00:08:03,020 --> 00:08:03,770
We are checking it right?

165
00:08:03,770 --> 00:08:05,000
We are not assigning it to be null.

166
00:08:05,000 --> 00:08:06,260
So that's an error.

167
00:08:06,260 --> 00:08:06,530
All right.

168
00:08:06,530 --> 00:08:07,730
So let's run it again.

169
00:08:07,730 --> 00:08:09,140
And yes it's working.

170
00:08:09,140 --> 00:08:10,490
So you can see we are getting true.

171
00:08:10,490 --> 00:08:15,620
That is we have checked that this binary tree over here is actually a valid binary search tree.

172
00:08:15,620 --> 00:08:19,490
Now let's just walk through the code and see what's happening over here.

173
00:08:19,760 --> 00:08:21,860
So again this is the binary tree.

174
00:08:21,860 --> 00:08:23,360
And then we are calling the function.

175
00:08:23,360 --> 00:08:24,620
So we are over here.

176
00:08:24,620 --> 00:08:26,840
Now we are calling the helper function.

177
00:08:26,840 --> 00:08:29,090
And we are passing the root node which is ten.

178
00:08:29,090 --> 00:08:30,710
So let's just take a pen and.

179
00:08:31,380 --> 00:08:32,310
See what's happening.

180
00:08:32,310 --> 00:08:36,900
So we are passing this node over here and then minus infinity and plus infinity.

181
00:08:36,930 --> 00:08:38,910
Now we are coming inside the helper function.

182
00:08:38,910 --> 00:08:41,220
We see that the node is not equal to null.

183
00:08:41,220 --> 00:08:44,400
So we come over here and we take the value which is ten.

184
00:08:44,400 --> 00:08:49,140
And we are checking is the value within the bounds minimum and maximum.

185
00:08:49,140 --> 00:08:52,410
At this point it's just minus infinity and plus infinity.

186
00:08:52,410 --> 00:08:54,510
So we don't get any of these.

187
00:08:54,540 --> 00:08:56,700
These none of these two conditions is true.

188
00:08:56,700 --> 00:08:57,030
Right.

189
00:08:57,030 --> 00:08:58,170
So we come over here.

190
00:08:58,170 --> 00:08:59,820
So we are done with this.

191
00:08:59,820 --> 00:09:00,930
So this is validated.

192
00:09:00,930 --> 00:09:06,270
Now we go ahead and over here we are going to check whether the left binary trees that is this part

193
00:09:06,270 --> 00:09:10,950
over here we are going to check whether this is a valid binary search tree or not.

194
00:09:10,950 --> 00:09:11,880
So let's go ahead.

195
00:09:11,880 --> 00:09:12,930
So we are over here.

196
00:09:13,500 --> 00:09:14,550
Now let's continue.

197
00:09:14,550 --> 00:09:16,530
Let's just change the color of the pen.

198
00:09:16,530 --> 00:09:18,270
Now we are past.

199
00:09:18,270 --> 00:09:19,830
We are again calling the helper function.

200
00:09:19,830 --> 00:09:23,190
We are passing node dot left which is this node over here.

201
00:09:23,190 --> 00:09:23,760
All right.

202
00:09:23,760 --> 00:09:26,760
And we are changing the maximum value.

203
00:09:26,760 --> 00:09:28,800
So min is still negative infinity.

204
00:09:28,800 --> 00:09:30,720
So min is negative infinity.

205
00:09:30,720 --> 00:09:33,300
And max is going to be the value which is ten.

206
00:09:33,300 --> 00:09:34,860
So max is going to be ten.

207
00:09:34,860 --> 00:09:35,280
All right.

208
00:09:35,280 --> 00:09:36,900
So we are inside the helper function.

209
00:09:36,900 --> 00:09:39,330
And we are checking is the node equal to null.

210
00:09:39,330 --> 00:09:40,590
No it's not equal to null.

211
00:09:40,590 --> 00:09:43,110
So we come over here we take the value which is five.

212
00:09:43,110 --> 00:09:44,760
And then we are checking is five.

213
00:09:44,760 --> 00:09:48,150
Within the bounds we know that minimum is negative infinity.

214
00:09:48,150 --> 00:09:49,410
So that's fine.

215
00:09:49,410 --> 00:09:54,120
So that's not going to be a problem because the value is anyway going to be greater than negative infinity.

216
00:09:54,120 --> 00:09:56,940
But then the maximum has to be equal to ten.

217
00:09:56,940 --> 00:09:57,810
So max is ten.

218
00:09:57,810 --> 00:09:59,310
So let's check.

219
00:09:59,310 --> 00:10:03,060
We are checking that over here is the value greater than equal to ten.

220
00:10:03,060 --> 00:10:04,380
No that's not the case right.

221
00:10:04,380 --> 00:10:06,120
Five is not greater than equal to ten.

222
00:10:06,120 --> 00:10:07,620
So we don't go inside over here.

223
00:10:07,620 --> 00:10:08,940
And then we come over here.

224
00:10:08,940 --> 00:10:10,710
So this has been validated.

225
00:10:10,710 --> 00:10:16,770
Now we are going to check is the left subtree of this particular node a valid binary search tree.

226
00:10:16,770 --> 00:10:18,720
So we are going to check this over here.

227
00:10:18,870 --> 00:10:19,380
All right.

228
00:10:19,380 --> 00:10:20,790
So this is what we are checking.

229
00:10:20,790 --> 00:10:22,920
And let me change the color of the pen.

230
00:10:22,920 --> 00:10:27,000
So we are coming over here and we are passing node dot left which is this node over here.

231
00:10:27,000 --> 00:10:28,020
So this is passed.

232
00:10:28,020 --> 00:10:32,790
And at this point we are going to change the maximum value to the value which is five.

233
00:10:32,790 --> 00:10:33,900
So value is five.

234
00:10:33,900 --> 00:10:37,380
So max is going to be five and min is still negative infinity.

235
00:10:37,380 --> 00:10:39,810
And again we are inside the helper function.

236
00:10:39,810 --> 00:10:42,150
Now over here node is not equal to null.

237
00:10:42,150 --> 00:10:43,980
So we still don't return true.

238
00:10:43,980 --> 00:10:46,110
And then we take this value which is three.

239
00:10:46,110 --> 00:10:50,010
And over here we are checking whether is three greater than equal to five.

240
00:10:50,010 --> 00:10:50,850
That's not true.

241
00:10:50,850 --> 00:10:54,360
And then value is it less than equal to negative infinity.

242
00:10:54,360 --> 00:10:56,010
That in anyway will not be true.

243
00:10:56,010 --> 00:10:56,280
Right.

244
00:10:56,280 --> 00:11:01,860
So we don't go inside over here and we come over here and we are going to check whether its left subtree

245
00:11:01,860 --> 00:11:06,630
is a valid binary search tree, at which point we are passing node dot left which is null.

246
00:11:06,630 --> 00:11:09,690
So when we come again inside the helper function, it will return true.

247
00:11:09,690 --> 00:11:13,110
So we have seen that its left subtree is a valid binary search tree.

248
00:11:13,110 --> 00:11:15,510
So now we are going to its right subtree right.

249
00:11:15,510 --> 00:11:19,740
So we come over here and we are passing this node which is four.

250
00:11:19,740 --> 00:11:21,750
So we are passing this four over here.

251
00:11:21,750 --> 00:11:24,960
And at this point we are going to change minimum to value.

252
00:11:24,960 --> 00:11:28,080
Value is equal to three and maximum is not changing.

253
00:11:28,080 --> 00:11:29,790
So maximum was already five right.

254
00:11:29,790 --> 00:11:31,350
So minimum is going to be three.

255
00:11:31,350 --> 00:11:33,270
And maximum is going to be five.

256
00:11:33,270 --> 00:11:35,550
So minimum is three and maximum is five.

257
00:11:35,550 --> 00:11:37,800
Again we come inside the helper function.

258
00:11:37,800 --> 00:11:39,540
We see that this node is not null.

259
00:11:39,540 --> 00:11:42,060
And we check is four within the bounds.

260
00:11:42,060 --> 00:11:44,910
So minimum is three and maximum is five.

261
00:11:44,910 --> 00:11:46,320
And the value over here is four.

262
00:11:46,320 --> 00:11:48,540
So it's actually within the bounds.

263
00:11:48,540 --> 00:11:50,550
So none of these two conditions is true.

264
00:11:50,550 --> 00:11:51,810
So we don't return false.

265
00:11:51,810 --> 00:11:56,340
So we come over here and we are checking whether its left subtree is a valid binary search tree.

266
00:11:56,340 --> 00:11:58,500
So we are passing node dot left which will be null.

267
00:11:58,500 --> 00:12:01,140
So again when we come over here we will just return true.

268
00:12:01,140 --> 00:12:06,030
And similarly when we come over here we will see that the right subtree is also a valid binary search

269
00:12:06,030 --> 00:12:06,210
tree.

270
00:12:06,210 --> 00:12:08,610
Because node dot right is just going to be null.

271
00:12:08,610 --> 00:12:08,940
All right.

272
00:12:08,940 --> 00:12:10,320
So again we come back.

273
00:12:10,320 --> 00:12:16,290
So we have seen that for node three its left and right subtree are valid binary search trees.

274
00:12:16,290 --> 00:12:18,990
So this over here this is going to return true.

275
00:12:18,990 --> 00:12:20,580
So this is going to return true.

276
00:12:20,580 --> 00:12:22,680
Now we go ahead and check this one over here.

277
00:12:22,680 --> 00:12:28,230
So we come over here and we will check whether this is actually a valid binary search tree which is

278
00:12:28,230 --> 00:12:30,390
the right subtree of node five.

279
00:12:30,390 --> 00:12:32,370
So let's just clear this space over here.

280
00:12:33,250 --> 00:12:34,090
So we are.

281
00:12:34,090 --> 00:12:35,590
We are coming over here now.

282
00:12:36,730 --> 00:12:40,480
So let me just make some make this clean so that we can keep track of this.

283
00:12:40,480 --> 00:12:42,190
So at this point.

284
00:12:43,060 --> 00:12:44,680
We come over here.

285
00:12:44,680 --> 00:12:49,900
So this this call will be part of is right BST where the current node is five.

286
00:12:49,900 --> 00:12:50,170
Right.

287
00:12:50,170 --> 00:12:53,710
So we are going to pass node dot right, which is this node over here.

288
00:12:53,710 --> 00:12:58,000
And then the value value is going to be five over here which is the min value.

289
00:12:58,000 --> 00:13:00,670
And the max value already was ten right at this point.

290
00:13:00,670 --> 00:13:02,290
So max is going to be ten.

291
00:13:02,290 --> 00:13:05,770
So we are going to check whether this node over here is in between 5 and 10.

292
00:13:05,770 --> 00:13:10,510
So that's going to be checked over here right when we again come inside the helper function with min

293
00:13:10,510 --> 00:13:11,890
as five and max is ten.

294
00:13:11,890 --> 00:13:13,720
So we see that the node is not null.

295
00:13:13,720 --> 00:13:15,610
So we take the value which is seven.

296
00:13:15,610 --> 00:13:19,120
And we are going to check is seven less than equal to five.

297
00:13:19,120 --> 00:13:20,170
No that's not true.

298
00:13:20,170 --> 00:13:22,090
And is seven greater than equal to ten.

299
00:13:22,090 --> 00:13:22,990
No that's not true.

300
00:13:22,990 --> 00:13:24,760
So we don't go we don't return false.

301
00:13:24,760 --> 00:13:29,140
So we come over here and we check for its left and right subtree because it's null.

302
00:13:29,140 --> 00:13:30,310
It will just return true.

303
00:13:30,310 --> 00:13:33,970
And in this way we have seen this also is going to return true.

304
00:13:33,970 --> 00:13:38,290
So for this particular node its left subtree is a binary search tree.

305
00:13:38,290 --> 00:13:39,520
So it returned true.

306
00:13:39,520 --> 00:13:42,490
And its right subtree is also a valid binary search tree.

307
00:13:42,490 --> 00:13:44,110
So this is also returning true.

308
00:13:44,110 --> 00:13:44,350
Right.

309
00:13:44,350 --> 00:13:46,180
So for this particular node right.

310
00:13:46,180 --> 00:13:49,300
So where the value was five this is going to be true.

311
00:13:49,300 --> 00:13:50,590
And this is going to be true.

312
00:13:50,590 --> 00:13:53,410
Therefore we will return true and true.

313
00:13:53,410 --> 00:13:58,780
So that means this is going to be true because both of these are true from this part we are going to

314
00:13:58,780 --> 00:13:59,860
return back true.

315
00:13:59,860 --> 00:14:05,830
So we have seen that when this was the node, its left subtree is actually a valid binary search tree.

316
00:14:05,830 --> 00:14:06,100
All right.

317
00:14:06,100 --> 00:14:11,230
So let me just make some space over here and clean this up a little bit so we can keep continuing to

318
00:14:11,230 --> 00:14:12,730
trace the code.

319
00:14:12,730 --> 00:14:17,290
So we have seen that this this was part of the call for the left binary search tree.

320
00:14:17,290 --> 00:14:19,630
This call over here right where the node was ten.

321
00:14:19,630 --> 00:14:21,070
Now this has returned.

322
00:14:21,070 --> 00:14:21,520
True.

323
00:14:21,520 --> 00:14:26,800
Now we proceed and we are going to check whether the right subtree which is this over here we are going

324
00:14:26,800 --> 00:14:30,580
to check whether this is actually a valid binary search tree or not.

325
00:14:30,580 --> 00:14:32,260
So that is part of this call over here.

326
00:14:32,260 --> 00:14:35,320
Now we are passing node dot right which is this node over here.

327
00:14:35,320 --> 00:14:37,540
And value is going to be ten.

328
00:14:37,540 --> 00:14:41,860
And maximum is just what was previously maximum which was infinity.

329
00:14:41,860 --> 00:14:47,410
So we come again inside the helper function min is going to be equal to ten and max is going to be infinity.

330
00:14:47,410 --> 00:14:50,140
So again we come over here the node is not null.

331
00:14:50,140 --> 00:14:52,030
So we are taking the value which is 20.

332
00:14:52,030 --> 00:14:55,720
Then we are checking is 20 less than equal to min which is ten.

333
00:14:55,720 --> 00:14:56,710
No that's not true.

334
00:14:56,710 --> 00:14:58,930
And is 20 greater than equal to infinity.

335
00:14:58,930 --> 00:14:59,590
That's not true.

336
00:14:59,590 --> 00:15:01,120
So we don't go inside over here.

337
00:15:01,120 --> 00:15:03,760
And then we come over here and we are proceeding.

338
00:15:03,760 --> 00:15:08,830
And we are going to check is the left subtree of this particular node a valid binary search tree or

339
00:15:08,830 --> 00:15:09,010
not.

340
00:15:09,010 --> 00:15:10,240
Which is this part over here.

341
00:15:10,240 --> 00:15:10,540
All right.

342
00:15:10,540 --> 00:15:12,160
So we are passing this node over here.

343
00:15:12,160 --> 00:15:13,570
And again we continue.

344
00:15:13,570 --> 00:15:13,750
Right.

345
00:15:13,750 --> 00:15:17,800
So over here min is going to be what was already min which is ten.

346
00:15:17,800 --> 00:15:20,650
And max is going to be the value which is 20.

347
00:15:20,650 --> 00:15:23,020
So we have ten and 20 as the value over here.

348
00:15:23,020 --> 00:15:25,000
And again we come inside the helper function.

349
00:15:25,000 --> 00:15:26,800
We see that this actually is valid.

350
00:15:26,800 --> 00:15:29,740
So it does not go, it does not continue and return false.

351
00:15:29,740 --> 00:15:34,000
So then we proceed and check is the left subtree of this one a valid binary search tree.

352
00:15:34,000 --> 00:15:38,080
And because it's just null it will come over here in that particular call and return true.

353
00:15:38,080 --> 00:15:40,750
So the left is a valid binary search tree.

354
00:15:40,750 --> 00:15:42,610
And we proceed and check for the right.

355
00:15:42,610 --> 00:15:44,710
Right which is over here for this call.

356
00:15:44,710 --> 00:15:45,790
Again we do the same thing.

357
00:15:45,790 --> 00:15:46,960
This is going to be the value.

358
00:15:46,960 --> 00:15:52,660
And then we check whether this is in between the uh the the value and max in that case.

359
00:15:52,660 --> 00:15:53,020
Right.

360
00:15:53,020 --> 00:15:55,720
So Max is is going to be at that point.

361
00:15:56,660 --> 00:15:58,940
20 and min is going to be 15.

362
00:15:58,940 --> 00:16:01,010
So 17 is in between these two values.

363
00:16:01,010 --> 00:16:02,270
So again, yes it's true.

364
00:16:02,270 --> 00:16:06,770
And we continue in this part to check whether its left subtree is a valid binary search tree.

365
00:16:06,770 --> 00:16:10,280
And because it's null it will just return true and its right subtree.

366
00:16:10,280 --> 00:16:15,560
Also we find is a valid binary search tree because we have 18 and 18 is greater than 17 and less than

367
00:16:15,560 --> 00:16:17,090
20, which are its bounds.

368
00:16:17,090 --> 00:16:19,580
So in this way this is going to return true.

369
00:16:19,580 --> 00:16:19,850
Right.

370
00:16:19,850 --> 00:16:24,140
So again its left also for node 15 return true because it was null.

371
00:16:24,140 --> 00:16:29,270
So we see that the left subtree over here is going to be true because this will return back true.

372
00:16:29,270 --> 00:16:30,530
This will return true.

373
00:16:30,530 --> 00:16:33,770
And then we will check for its right subtree and we will pass 30.

374
00:16:33,770 --> 00:16:39,650
And then the bounds are going to be that it should be less than infinity but greater than 20.

375
00:16:39,650 --> 00:16:40,700
And we see that its true.

376
00:16:40,700 --> 00:16:43,040
Again it will check over here whether its violated.

377
00:16:43,040 --> 00:16:44,090
It's not violated.

378
00:16:44,090 --> 00:16:48,950
So we are going to check for its left and right subtree which will return true because it's just null.

379
00:16:48,950 --> 00:16:51,650
And then we will just return that this is true.

380
00:16:51,650 --> 00:16:53,720
So this also will return back true.

381
00:16:53,720 --> 00:16:57,200
So for this node we get back from the left and right true.

382
00:16:57,200 --> 00:16:59,900
So this is also going to return back true.

383
00:16:59,900 --> 00:17:04,430
And then when the when we called the is right BST function right.

384
00:17:04,430 --> 00:17:09,260
So this one over here when we call the helper function passing this node over here this is going to

385
00:17:09,260 --> 00:17:09,830
return true.

386
00:17:09,830 --> 00:17:17,540
So for the node ten is left BST is true and is right BST is also equal to two is also equal to true.

387
00:17:17,540 --> 00:17:20,150
And because both of these are equal to true.

388
00:17:20,150 --> 00:17:23,990
So we are just going to return true when from for over here.

389
00:17:23,990 --> 00:17:24,170
Right.

390
00:17:24,170 --> 00:17:26,720
For this call for the first call this is going to return.

391
00:17:26,720 --> 00:17:30,170
True because we have seen this and this is going to be giving back.

392
00:17:30,170 --> 00:17:30,560
True.

393
00:17:30,560 --> 00:17:36,260
So in this way we have identified that the given binary tree which is given to us is actually a valid

394
00:17:36,260 --> 00:17:37,250
binary search tree.

395
00:17:37,700 --> 00:17:43,100
Now let me just clear this up and let's take a quick look at the space and time complexity of this solution.

396
00:17:43,100 --> 00:17:45,320
Now what's going to be the time complexity.

397
00:17:45,320 --> 00:17:50,420
The time complexity is going to be O of N, because you can see we have to traverse through every node

398
00:17:50,420 --> 00:17:53,810
over here and check whether it's within the bounds.

399
00:17:53,810 --> 00:17:56,780
And then we proceed and check for its left and right subtree.

400
00:17:56,780 --> 00:18:00,410
So the time complexity is going to be O of n because we have to traverse every node.

401
00:18:00,410 --> 00:18:07,160
And the space complexity is going to be O of height or the maximum depth of this tree, because this

402
00:18:07,160 --> 00:18:08,720
is going to be a recursive solution.

403
00:18:08,720 --> 00:18:11,210
And we're going to take up space on the call stack.

404
00:18:11,210 --> 00:18:13,100
And in the worst case.

405
00:18:13,870 --> 00:18:19,960
The space complexity is going to be O of N, because if the binary tree was something like this, right

406
00:18:19,960 --> 00:18:22,450
where we just have nodes in one direction.

407
00:18:22,450 --> 00:18:23,860
So this looks like a linked list.

408
00:18:23,860 --> 00:18:25,990
So in this case we would have to go all the way down.

409
00:18:25,990 --> 00:18:26,230
Right.

410
00:18:26,230 --> 00:18:30,220
So in that case the call stack is going to take space of the order of n.

411
00:18:30,220 --> 00:18:34,150
So that's why in the worst case the space complexity is going to be O of n.