1
00:00:00,530 --> 00:00:01,520
Welcome back.

2
00:00:01,520 --> 00:00:05,300
In this video, let's think about how we can solve this question.

3
00:00:05,300 --> 00:00:11,720
First let's go ahead and create a binary search tree which is valid now for the root node.

4
00:00:11,720 --> 00:00:13,850
Let me have any value which is ten.

5
00:00:13,850 --> 00:00:20,330
Now we can notice that if we have any value over here, which is between minus infinity and infinity,

6
00:00:20,330 --> 00:00:21,980
that means any value, right?

7
00:00:21,980 --> 00:00:24,770
Then also our binary search tree would be valid.

8
00:00:24,770 --> 00:00:30,290
So let me write the limits over here so I can have any value over here which is between minus infinity

9
00:00:30,290 --> 00:00:31,340
and infinity.

10
00:00:31,370 --> 00:00:35,630
Now let's say I want to insert a node to the left of this particular node.

11
00:00:35,630 --> 00:00:38,870
So for example I can insert the value five over here.

12
00:00:38,870 --> 00:00:46,280
Now any value which I insert over here will be valid if it is between negative infinity and ten, because

13
00:00:46,280 --> 00:00:51,050
the value towards the left of this particular node has to be strictly less than ten, right?

14
00:00:51,050 --> 00:00:56,600
So the limits for the value which I can have over here is minus infinity and ten.

15
00:00:56,600 --> 00:01:01,340
So I can say minus infinity less than the value and then less than ten.

16
00:01:01,340 --> 00:01:02,540
So over here we have five.

17
00:01:02,540 --> 00:01:03,740
Now this is satisfied.

18
00:01:03,740 --> 00:01:05,000
That's why this is valid.

19
00:01:05,000 --> 00:01:10,070
Now let's say I want to insert something to the right over here for this particular node.

20
00:01:10,070 --> 00:01:11,420
So what would be the limit.

21
00:01:11,450 --> 00:01:13,970
Now I just need something greater than ten right.

22
00:01:13,970 --> 00:01:17,720
So for example let me insert the node with value 20 over here.

23
00:01:18,170 --> 00:01:20,180
Now let's think about the bounds.

24
00:01:20,180 --> 00:01:23,960
Now if I want to insert any value over here now 20 is a valid case.

25
00:01:23,960 --> 00:01:26,120
Now what would I be thinking about.

26
00:01:26,120 --> 00:01:26,360
Right.

27
00:01:26,360 --> 00:01:28,280
So what is the limits that I'm thinking about.

28
00:01:28,280 --> 00:01:30,770
I should have something which is greater than ten.

29
00:01:30,770 --> 00:01:35,420
And then it has to be just less than infinity, which means that it can be anything.

30
00:01:35,420 --> 00:01:38,120
So it can be 200, 2000 or 20,000.

31
00:01:38,120 --> 00:01:44,990
So I can say that the limits for whatever I'm putting over here is ten less than 20 less than infinity.

32
00:01:45,200 --> 00:01:46,280
Now let's go ahead.

33
00:01:46,280 --> 00:01:51,800
Let's try to insert something to the left of this particular node over here again, because it's towards

34
00:01:51,800 --> 00:01:55,910
the left of this node, we know that it has to be less than the value five over here.

35
00:01:55,910 --> 00:01:58,460
So for example I can take the value three.

36
00:01:58,490 --> 00:02:02,690
Now again what are the limits for any value that I want to insert over here.

37
00:02:02,690 --> 00:02:07,250
Any value which satisfies which is less than five right will be valid over here.

38
00:02:07,250 --> 00:02:12,530
So I can say it just has to be greater than negative infinity, which means that it can be anything,

39
00:02:12,530 --> 00:02:15,050
but it has to be less than five.

40
00:02:15,050 --> 00:02:15,530
All right.

41
00:02:15,530 --> 00:02:20,270
So that's the range for values that are possible for this node over here.

42
00:02:20,270 --> 00:02:23,840
Now let's try to insert something to the right of this particular node.

43
00:02:23,840 --> 00:02:26,330
In that case it becomes interesting right.

44
00:02:26,330 --> 00:02:28,160
It has to be greater than five.

45
00:02:28,160 --> 00:02:32,720
But because it's towards the left of ten it still has to be less than ten.

46
00:02:32,720 --> 00:02:34,400
So what is a possible value.

47
00:02:34,400 --> 00:02:36,710
Let's say seven seven is a possible value.

48
00:02:36,710 --> 00:02:38,270
So I can have seven over here.

49
00:02:38,720 --> 00:02:42,680
Now to generalize the limits for what value can come over here.

50
00:02:42,680 --> 00:02:46,250
It has to be greater than five but less than ten.

51
00:02:46,250 --> 00:02:51,560
So I can say five less than seven less than ten and seven is the value that we have just chosen.

52
00:02:51,560 --> 00:02:54,860
So anything which is between 5 and 10 would have worked over here.

53
00:02:54,860 --> 00:02:59,450
Now let's go ahead and insert something to the left of this particular node over here.

54
00:02:59,450 --> 00:03:01,700
For example I can have 15 right.

55
00:03:01,700 --> 00:03:06,740
So it just has to be greater than 1010 which is this node over here because it's towards the right of

56
00:03:06,740 --> 00:03:07,130
ten.

57
00:03:07,130 --> 00:03:09,170
But it has to be less than 20.

58
00:03:09,170 --> 00:03:12,170
So it has to be in between 10 and 20.

59
00:03:12,170 --> 00:03:14,120
So for example 15 works.

60
00:03:14,120 --> 00:03:20,210
Now the limits to generalize for what can come over here would be ten less than 15 less than 20.

61
00:03:20,240 --> 00:03:24,230
Similarly, let's insert something to the right of this particular node over here.

62
00:03:24,230 --> 00:03:25,910
For example I can have 30.

63
00:03:25,910 --> 00:03:29,870
Now the condition for this is just that it has to be greater than 20, right.

64
00:03:29,870 --> 00:03:31,580
So it has to be greater than 20.

65
00:03:31,580 --> 00:03:36,710
And I can say it can be less than infinity, which means it can go as high as it wants.

66
00:03:36,710 --> 00:03:38,420
So we have 30 over here.

67
00:03:38,420 --> 00:03:39,560
Now let's continue.

68
00:03:39,560 --> 00:03:41,270
Let's try to insert something over here.

69
00:03:41,270 --> 00:03:42,980
So let's say we have four.

70
00:03:42,980 --> 00:03:45,770
So again over here the condition is interesting.

71
00:03:45,770 --> 00:03:48,020
It has to be greater than ten right.

72
00:03:48,020 --> 00:03:52,160
And so sorry it has to be less than ten because it's towards the left of ten.

73
00:03:52,160 --> 00:03:56,090
And it has to be less than five because it's towards the left of five.

74
00:03:56,090 --> 00:03:56,390
Right.

75
00:03:56,390 --> 00:03:58,430
But it has to be greater than three.

76
00:03:58,430 --> 00:04:02,570
So we can say that the limits are between 3 and 5 over here.

77
00:04:02,570 --> 00:04:05,840
So it has to be greater than three but less than five.

78
00:04:05,840 --> 00:04:12,470
So I can say whatever value I insert over here has to be in between 3 and 5 and four satisfies that.

79
00:04:12,470 --> 00:04:14,630
Now let's go ahead and insert something over here.

80
00:04:14,630 --> 00:04:19,520
So let's say I want to insert to the left of this particular node to the right of this particular node.

81
00:04:19,520 --> 00:04:19,820
All right.

82
00:04:19,820 --> 00:04:21,500
So let's take right in this case.

83
00:04:22,160 --> 00:04:28,100
Now, if I want to insert something to the right of this 15 over here, it has to be greater than 15.

84
00:04:28,100 --> 00:04:32,120
But because it's part of the left of 20, it has to be less than 20.

85
00:04:32,150 --> 00:04:32,420
Right.

86
00:04:32,420 --> 00:04:33,470
So 17 works.

87
00:04:33,470 --> 00:04:34,700
So let's try 17.

88
00:04:34,700 --> 00:04:38,930
Now to generalize the condition is that it has to be between 15 and 20.

89
00:04:38,930 --> 00:04:42,260
So we have 15 less than 17 less than 20.

90
00:04:42,290 --> 00:04:44,930
Similarly I can insert 18 over here right.

91
00:04:44,930 --> 00:04:46,340
So I can have 18.

92
00:04:46,340 --> 00:04:48,470
So what's the criteria for this.

93
00:04:48,740 --> 00:04:53,840
For 18 it has to be greater than whatever we have over here which is 17 right.

94
00:04:53,840 --> 00:04:58,400
It has to be greater than 17 but it has to be less than 20, which is what we have over here.

95
00:04:58,400 --> 00:05:02,030
So I can say 17 less than 18, less than 20.

96
00:05:02,030 --> 00:05:02,660
All right.

97
00:05:02,660 --> 00:05:07,340
So we have just seen how we construct a valid binary search tree.

98
00:05:07,340 --> 00:05:13,220
So what is the thinking that would go on in our head when we go ahead and construct a valid binary search

99
00:05:13,220 --> 00:05:13,550
tree.

100
00:05:13,550 --> 00:05:20,090
Now let's try to look at a pattern which is there over here so that we can use it to solve the question.

101
00:05:20,090 --> 00:05:24,500
Now we started with ten and we have seen that any value is fine at the root.

102
00:05:24,500 --> 00:05:28,490
Now when we wanted to insert something to the left of this node, right.

103
00:05:28,490 --> 00:05:34,580
So when we travel towards the left, you can see that we changed the maximum value over here it was

104
00:05:34,580 --> 00:05:35,210
infinity.

105
00:05:35,210 --> 00:05:38,330
We changed that to the previous value which was ten.

106
00:05:38,330 --> 00:05:40,670
Again, when we move towards the left right.

107
00:05:40,670 --> 00:05:45,440
Towards the left you can see we get we are again changing the maximum value from 10 to 5.

108
00:05:45,440 --> 00:05:51,440
Now when we move towards the right towards this direction, let's say we start again from ten.

109
00:05:51,440 --> 00:05:56,120
When we move towards the right, you can see that we are changing the minimum value.

110
00:05:56,120 --> 00:05:58,550
Over here the minimum was minus infinity.

111
00:05:58,550 --> 00:06:02,030
But when we move towards the right that changed to ten again.

112
00:06:02,030 --> 00:06:06,650
When we move in the direction that is towards the right, we are changing the minimum value which is

113
00:06:06,650 --> 00:06:07,220
20.

114
00:06:07,220 --> 00:06:10,520
So from ten we are changing it to 20 which is this value over here.

115
00:06:10,520 --> 00:06:14,030
So this is the interesting pattern which we will use to solve this question.

116
00:06:14,030 --> 00:06:15,170
Again you can notice over here.

117
00:06:15,170 --> 00:06:17,540
From here we have this criteria.

118
00:06:17,540 --> 00:06:23,900
When we move towards the right we are changing the minimum value again from minus infinity to five over

119
00:06:23,900 --> 00:06:24,200
here.

120
00:06:24,200 --> 00:06:29,150
So whenever we are moving towards the left we are changing the maximum value.

121
00:06:29,150 --> 00:06:35,240
And whenever we are moving towards the right, we are changing the minimum value for the value of that

122
00:06:35,240 --> 00:06:40,700
particular node to be valid, such that the given binary tree is a binary search tree.

123
00:06:40,700 --> 00:06:42,830
So this is how we are going to solve this question.

124
00:06:42,830 --> 00:06:43,190
All right.

125
00:06:43,190 --> 00:06:47,660
So we will have a recursive function and we start at the root node.

126
00:06:47,660 --> 00:06:51,230
So when we are at the node we will check whether it's between the bounds.

127
00:06:51,230 --> 00:06:56,450
And initially we will just say that the value for the root node has to be between minus infinity and

128
00:06:56,450 --> 00:06:59,600
infinity, so that any value is fine at the root node.

129
00:06:59,600 --> 00:07:07,100
Then we will have a call and to check whether its left subtree, which is this part over here is a valid

130
00:07:07,100 --> 00:07:08,060
binary search tree.

131
00:07:08,060 --> 00:07:13,520
And we will have a call to check whether its right subtree, which is this tree over here is a valid

132
00:07:13,520 --> 00:07:14,480
binary search tree.

133
00:07:14,480 --> 00:07:20,510
Now if these two are valid binary search trees, then we will return true and if not we will return

134
00:07:20,510 --> 00:07:20,780
false.

135
00:07:20,780 --> 00:07:22,040
So this is how we will do it right?

136
00:07:22,040 --> 00:07:23,810
So it's going to be a recursive call.

137
00:07:24,290 --> 00:07:26,510
So let's just see the recursion happening.

138
00:07:26,510 --> 00:07:28,850
So first we start at this node over here.

139
00:07:28,850 --> 00:07:35,090
And then to check whether its left subtree is a valid binary search tree we will move in this direction.

140
00:07:35,090 --> 00:07:42,080
So when we reach this node we will check whether the value for this node is in between the range minus

141
00:07:42,080 --> 00:07:43,040
infinity to ten.

142
00:07:43,040 --> 00:07:43,220
Right.

143
00:07:43,220 --> 00:07:48,650
So for this we are just changing the max value from infinity, which was the previous upper limit to

144
00:07:48,650 --> 00:07:50,060
this value over here which is ten.

145
00:07:50,060 --> 00:07:52,940
So again we get the limits minus infinity and ten.

146
00:07:52,940 --> 00:07:57,080
And we will check whether the value over here is in between these bounds.

147
00:07:57,080 --> 00:08:03,080
Now if that is not the case then we would just return false because we have identified that the tree

148
00:08:03,080 --> 00:08:04,970
would not be a valid binary search tree.

149
00:08:04,970 --> 00:08:12,140
But if it is true, we will proceed and check whether its left subtree and its right subtree is a valid

150
00:08:12,140 --> 00:08:13,640
binary search tree or not.

151
00:08:13,640 --> 00:08:14,510
So let's proceed.

152
00:08:14,510 --> 00:08:15,950
So over here we can see it's true.

153
00:08:15,950 --> 00:08:21,200
So to check whether its left subtree is a valid binary search tree, we again move in this direction

154
00:08:21,200 --> 00:08:26,810
which is towards the left and we are changing the maximum value from 10 to 5, which is the value over

155
00:08:26,810 --> 00:08:26,990
here.

156
00:08:26,990 --> 00:08:27,290
Right.

157
00:08:27,290 --> 00:08:30,800
So the range now has to be in between minus infinity and five.

158
00:08:30,800 --> 00:08:34,430
And for this node we check whether the value is in between this range.

159
00:08:34,430 --> 00:08:36,080
We see it's in that range.

160
00:08:36,080 --> 00:08:37,460
So we proceed.

161
00:08:37,460 --> 00:08:39,890
If it was not so we would have just returned false.

162
00:08:39,890 --> 00:08:45,410
Now we are going to check whether its left subtree and whether its right subtree is a valid binary search

163
00:08:45,410 --> 00:08:45,770
tree.

164
00:08:45,770 --> 00:08:48,350
Now the left is nothing over here we just have null.

165
00:08:48,350 --> 00:08:50,180
So we go ahead for the right part.

166
00:08:50,210 --> 00:08:56,540
Now we move in this direction and when we move towards the right, we are going to change the minimum

167
00:08:56,540 --> 00:08:57,020
value right.

168
00:08:57,020 --> 00:09:02,090
So the minimum is minus infinity over here that's going to be changed to this value which is three.

169
00:09:02,090 --> 00:09:05,780
So we have the bounds as three and five for this particular node.

170
00:09:05,780 --> 00:09:08,510
And we are checking whether the value is in that range.

171
00:09:08,510 --> 00:09:10,790
And we see it is it's the case.

172
00:09:10,790 --> 00:09:17,270
So by now we have established that the left subtree of this particular node is a valid binary search

173
00:09:17,270 --> 00:09:17,600
tree.

174
00:09:17,600 --> 00:09:21,500
So we are now going to check whether its right subtree is a valid binary search.

175
00:09:21,840 --> 00:09:27,690
So we reach this node over here and we check whether this node is in the range which is five and ten.

176
00:09:27,690 --> 00:09:27,900
Right.

177
00:09:27,900 --> 00:09:29,250
So how do we get five and ten.

178
00:09:29,250 --> 00:09:31,410
We have minus infinity and ten over here.

179
00:09:31,410 --> 00:09:33,270
And we are moving in the right direction.

180
00:09:33,270 --> 00:09:36,810
So we're going to change the minimum value from minus infinity to five.

181
00:09:36,810 --> 00:09:39,420
So we will get five and ten as the range.

182
00:09:39,420 --> 00:09:41,400
And we see that it's in that range.

183
00:09:41,400 --> 00:09:47,280
So we have by now identified that the left subtree of this particular node right.

184
00:09:47,280 --> 00:09:50,940
So that is this part over here is a valid binary search tree.

185
00:09:50,940 --> 00:09:56,190
So now we will move in the right direction to check whether the right subtree is a valid binary search

186
00:09:56,190 --> 00:09:56,400
tree.

187
00:09:56,400 --> 00:09:57,450
So we go over here.

188
00:09:57,450 --> 00:09:59,070
Now we come to this node.

189
00:09:59,070 --> 00:10:02,250
Now when we move towards the right we will change the minimum.

190
00:10:02,250 --> 00:10:05,640
So the minimum is changed from minus infinity to ten over here.

191
00:10:05,640 --> 00:10:10,710
And we will check whether the value over here in this node is in between ten and infinity.

192
00:10:10,740 --> 00:10:12,150
Now we see that it is.

193
00:10:12,150 --> 00:10:14,010
Yes it is indeed in this range.

194
00:10:14,010 --> 00:10:19,920
So now we are going to check whether its left subtree and whether its right subtree is a valid binary

195
00:10:19,920 --> 00:10:21,090
search tree or not.

196
00:10:21,090 --> 00:10:27,300
So let's proceed to check whether the left subtree of this particular node is a valid binary search

197
00:10:27,300 --> 00:10:27,660
tree.

198
00:10:27,660 --> 00:10:31,080
We move in this direction and we reach this node over here.

199
00:10:31,080 --> 00:10:35,340
Now we are moving left, so when we move left we will change the maximum.

200
00:10:35,340 --> 00:10:37,320
So the maximum over here is infinity.

201
00:10:37,320 --> 00:10:39,570
That's changed to this value which is 20.

202
00:10:39,570 --> 00:10:41,790
So we get that the bounds are ten and 20.

203
00:10:41,790 --> 00:10:45,990
And we're going to check whether the value of this node is in between 10 and 20.

204
00:10:45,990 --> 00:10:49,410
Now if it was not the case we would have just returned false.

205
00:10:49,410 --> 00:10:51,510
But we see that yes it's in that range.

206
00:10:51,510 --> 00:10:57,360
So we proceed and check whether its left subtree and its right subtree are valid binary search trees

207
00:10:57,360 --> 00:10:57,930
or not.

208
00:10:57,930 --> 00:10:59,280
So over here we just have null.

209
00:10:59,280 --> 00:11:00,810
So we proceed to the right part.

210
00:11:00,810 --> 00:11:02,280
So we come to this node.

211
00:11:02,280 --> 00:11:05,850
And when we move towards the right we are going to change the minimum.

212
00:11:05,850 --> 00:11:08,550
So the minimum from ten is changed to 15.

213
00:11:08,550 --> 00:11:11,280
So our range now is between 15 and 20.

214
00:11:11,280 --> 00:11:15,210
And we are checking whether the value at this node is between 15 and 20.

215
00:11:15,240 --> 00:11:17,040
We see that yes that's the case.

216
00:11:17,040 --> 00:11:22,560
So we will check whether its left subtree and its right subtree are valid binary search trees or not.

217
00:11:22,560 --> 00:11:24,360
So towards the left we just have null.

218
00:11:24,360 --> 00:11:25,560
So we go to the right.

219
00:11:25,560 --> 00:11:29,220
And again because we are moving towards the right we will change the minimum.

220
00:11:29,220 --> 00:11:32,130
So from 15 we change the minimum to 17.

221
00:11:32,130 --> 00:11:33,420
So 17 and 20.

222
00:11:33,420 --> 00:11:34,590
So that's the range now.

223
00:11:34,590 --> 00:11:36,000
And we are checking this value.

224
00:11:36,000 --> 00:11:37,500
Is it between 17 and 20.

225
00:11:37,500 --> 00:11:39,900
Yes 18 is between 17 and 20.

226
00:11:39,900 --> 00:11:42,510
So yes we see that this is also true.

227
00:11:42,510 --> 00:11:43,230
The value is true.

228
00:11:43,230 --> 00:11:45,150
It's following the binary search tree property.

229
00:11:45,150 --> 00:11:51,300
So by now we have established that the left subtree of this particular node is a valid binary search

230
00:11:51,300 --> 00:11:51,630
tree.

231
00:11:51,630 --> 00:11:53,610
And hence we are going to move towards the right.

232
00:11:53,610 --> 00:11:54,750
So we come over here.

233
00:11:54,750 --> 00:11:58,410
Now when we move towards the right we are going to change the minimum right.

234
00:11:58,410 --> 00:12:00,510
So ten is now going to be changed to 20.

235
00:12:00,510 --> 00:12:03,240
So we have 20 and infinity as the range.

236
00:12:03,240 --> 00:12:08,070
And then we are going to check whether the value of this node is between 20 and infinity.

237
00:12:08,070 --> 00:12:09,930
And we see that yes that's the case.

238
00:12:09,930 --> 00:12:16,200
So that means by now we have identified that previously we we we've identified that the left subtree

239
00:12:16,200 --> 00:12:18,540
over here was a valid binary search tree.

240
00:12:18,540 --> 00:12:24,030
And by now we have identified that the right subtree for this particular node is a valid binary search

241
00:12:24,030 --> 00:12:24,330
tree.

242
00:12:24,330 --> 00:12:27,120
So this will return true and this will return true.

243
00:12:27,120 --> 00:12:31,050
And then because this and this is true, we will just return true.

244
00:12:31,050 --> 00:12:36,630
Which means that the given binary tree which is given to us is indeed a valid binary search tree.

245
00:12:36,630 --> 00:12:38,700
So this is how we will solve this question.

246
00:12:38,700 --> 00:12:42,930
Now let's take a quick look at the time and space complexity of this solution.

247
00:12:42,930 --> 00:12:47,880
So when it comes to the time complexity, we have to traverse every node, right.

248
00:12:47,880 --> 00:12:51,030
So that's why the time complexity is going to be O of n.

249
00:12:51,030 --> 00:12:57,000
So we have to traverse every node and check whether it is between the particular range which is applicable

250
00:12:57,000 --> 00:12:58,860
for a value in that place.

251
00:12:58,860 --> 00:12:59,130
Right.

252
00:12:59,130 --> 00:13:04,560
So after going to a particular node we're just doing some constant time operations which is checking

253
00:13:04,560 --> 00:13:06,510
whether it is within the bounds.

254
00:13:06,510 --> 00:13:09,660
So that's why the time complexity of this solution is O of n.

255
00:13:09,660 --> 00:13:15,720
And the space complexity of this solution is going to be O of the maximum depth or the height of the

256
00:13:15,720 --> 00:13:16,830
given binary tree.

257
00:13:16,830 --> 00:13:17,040
Right.

258
00:13:17,040 --> 00:13:20,340
Because that's because this is going to be a recursive solution.

259
00:13:20,340 --> 00:13:23,400
And then because we are going to take up space on the call stack.

260
00:13:23,400 --> 00:13:26,490
So that's why the space complexity is O of H.

261
00:13:26,490 --> 00:13:33,030
Now in the worst case this is going to be O of n because that is the case where the binary tree looks

262
00:13:33,030 --> 00:13:34,140
like a linked list, right.

263
00:13:34,140 --> 00:13:35,310
Which is something like this.

264
00:13:35,310 --> 00:13:37,890
Every node is going towards the right for example.

265
00:13:37,890 --> 00:13:40,710
So in this case we have to go all the way down.

266
00:13:40,710 --> 00:13:46,110
So that's why we can say that in the worst case the space complexity is going to be O of n.