1
00:00:00,450 --> 00:00:01,470
Welcome back.

2
00:00:01,470 --> 00:00:04,350
Let's now think how we can solve this question.

3
00:00:04,350 --> 00:00:07,800
Let's say the array which is given to us is one, two, three, four, five.

4
00:00:07,800 --> 00:00:10,170
And let's try to make a few observations.

5
00:00:10,170 --> 00:00:14,880
Now we know that we have to convert this into a height balanced binary search tree.

6
00:00:14,880 --> 00:00:17,100
And for this we will have some element.

7
00:00:17,100 --> 00:00:22,050
Some element among these values is going to be made the root right of the binary search tree.

8
00:00:22,050 --> 00:00:28,950
Now we know that this will be height balanced only if the depth of the two subtrees does not differ

9
00:00:28,950 --> 00:00:30,150
by more than one.

10
00:00:30,150 --> 00:00:37,680
So this means that we should have the same or almost the same number of nodes in the left part and the

11
00:00:37,680 --> 00:00:39,780
right part of this root node right.

12
00:00:39,780 --> 00:00:41,760
This is the left part and this is the right part.

13
00:00:41,790 --> 00:00:46,410
Now if you're just filling everything into its right and nothing into its left, then this is not going

14
00:00:46,410 --> 00:00:47,280
to be height balanced.

15
00:00:47,280 --> 00:00:53,160
So to make it height balanced, that is to ensure that the depth of the two subtrees, the left and

16
00:00:53,160 --> 00:00:55,470
the right subtrees does not differ by more than one.

17
00:00:55,470 --> 00:01:01,140
We have to have the same or almost the same number of nodes in the left and right of the root.

18
00:01:01,140 --> 00:01:02,850
So this is an interesting observation.

19
00:01:02,850 --> 00:01:08,520
So this can be possible if we just pick the middle value as the root right.

20
00:01:08,520 --> 00:01:14,610
Then you can see that we have an equal number of items towards its left and towards its right.

21
00:01:14,610 --> 00:01:17,310
Now why do we have almost the same over here?

22
00:01:17,850 --> 00:01:21,600
For example, if the array which is given to us is one, two, three, four, five.

23
00:01:21,600 --> 00:01:26,580
Now if you are taking the middle as left plus right divided by two, that is, this is index zero.

24
00:01:26,580 --> 00:01:28,620
This is index one, this is two, this is three.

25
00:01:28,620 --> 00:01:33,240
So if you do zero plus three by two and then we are flooring it, we will get one as the middle element.

26
00:01:33,240 --> 00:01:33,390
Right.

27
00:01:33,390 --> 00:01:34,680
So this would be the middle element.

28
00:01:34,680 --> 00:01:36,960
Now on its left we just have one element.

29
00:01:36,960 --> 00:01:38,520
And on its right we have two.

30
00:01:38,520 --> 00:01:41,760
But that is okay because the depth can differ by one.

31
00:01:41,760 --> 00:01:42,840
So that's not a problem.

32
00:01:42,840 --> 00:01:44,790
So that's why we have almost the same.

33
00:01:44,790 --> 00:01:50,490
So we need either the same or almost the same nodes in the left and the right of the root.

34
00:01:50,490 --> 00:01:55,740
So that means that we have understood we have to pick the middle value in the sorted array, which is

35
00:01:55,740 --> 00:01:59,040
given to us, and make it the root of the binary search tree.

36
00:01:59,040 --> 00:02:03,240
And again, remember the array which is given to us is strictly increasing.

37
00:02:03,240 --> 00:02:05,550
So we just have to pick the middle value.

38
00:02:05,550 --> 00:02:07,680
There is no possibility that this is going to be two.

39
00:02:07,680 --> 00:02:09,810
This is two and this is also two etc..

40
00:02:09,810 --> 00:02:10,080
Right.

41
00:02:10,080 --> 00:02:11,940
So because it is strictly increasing.

42
00:02:11,940 --> 00:02:17,640
So we just have to pick the middle value and we can be sure that there's going to be the same or almost

43
00:02:17,640 --> 00:02:21,720
the same nodes in the left and the right of the middle value.

44
00:02:21,720 --> 00:02:22,200
All right.

45
00:02:22,200 --> 00:02:23,670
So this is an interesting observation.

46
00:02:23,670 --> 00:02:27,600
So let's go ahead and try to implement this and proceed with our solution.

47
00:02:27,600 --> 00:02:30,750
So over here let's say this is the array which is given to us.

48
00:02:30,750 --> 00:02:32,760
And let's write the indices of the given array.

49
00:02:32,760 --> 00:02:35,670
So we have zero till eight as the indices.

50
00:02:35,670 --> 00:02:40,230
And we are going to have a left pointer and the right pointer to identify the middle value.

51
00:02:40,230 --> 00:02:43,470
Now middle at this point is going to be zero plus eight by two.

52
00:02:43,470 --> 00:02:46,710
And then we're just going to floor it which is equal to four.

53
00:02:46,710 --> 00:02:51,570
So we get that middle is pointing at index four which has the value five.

54
00:02:51,570 --> 00:02:55,770
And as we've seen in the previous section we are going to make this the root node.

55
00:02:55,770 --> 00:02:57,780
So let's make a node out of this.

56
00:02:57,780 --> 00:03:00,570
And this is going to be the root node of the binary search tree.

57
00:03:00,570 --> 00:03:02,400
So we have already used this up.

58
00:03:02,400 --> 00:03:02,880
All right.

59
00:03:02,910 --> 00:03:08,640
Now what we are going to do is we are going to recursively call the same function on the left part,

60
00:03:08,640 --> 00:03:11,490
which is this part and the right part of the array.

61
00:03:11,490 --> 00:03:13,350
And we are just going to make notes.

62
00:03:13,350 --> 00:03:13,530
Right.

63
00:03:13,530 --> 00:03:15,660
So we are just going to do this recursively.

64
00:03:15,660 --> 00:03:18,420
So always the middle value is going to be made into a node.

65
00:03:18,420 --> 00:03:24,150
And then it's going to be either the left node or the right node for the particular node where we are

66
00:03:24,150 --> 00:03:24,390
at.

67
00:03:24,390 --> 00:03:26,910
So let's try to understand this in a better manner.

68
00:03:27,300 --> 00:03:28,920
Now why do we need to do this.

69
00:03:28,920 --> 00:03:31,590
Why do we need to keep recursively doing this.

70
00:03:31,590 --> 00:03:33,360
Now let's try to make an observation.

71
00:03:33,360 --> 00:03:35,970
So we have already got five as our root node.

72
00:03:35,970 --> 00:03:41,940
Now we cannot just insert all of these values in any order on the left side of the particular root node.

73
00:03:41,940 --> 00:03:42,240
Right.

74
00:03:42,240 --> 00:03:43,080
We cannot do that.

75
00:03:43,080 --> 00:03:45,000
That alone will not be sufficient.

76
00:03:45,000 --> 00:03:45,750
Why is that so?

77
00:03:45,750 --> 00:03:47,730
Because I could have an insertion like this.

78
00:03:47,730 --> 00:03:49,650
I could insert one towards its left.

79
00:03:49,650 --> 00:03:55,920
And then if are if we are inserting two, three and four towards the left of the node five, it's all

80
00:03:55,920 --> 00:03:58,800
going to be over here because these are greater than one right now.

81
00:03:58,800 --> 00:04:01,200
In this case you can see 1234.

82
00:04:01,200 --> 00:04:02,790
So we have four nodes.

83
00:04:02,790 --> 00:04:04,590
And there is nothing over here.

84
00:04:04,590 --> 00:04:04,740
Right.

85
00:04:04,740 --> 00:04:06,990
So you can see this is not going to be height balanced.

86
00:04:06,990 --> 00:04:09,090
This part over here is not height balanced.

87
00:04:09,090 --> 00:04:11,910
So you have 01233 edges over here.

88
00:04:11,910 --> 00:04:15,270
And you have zero edges on its left part of this particular node.

89
00:04:15,270 --> 00:04:16,590
So this is not height balanced.

90
00:04:16,590 --> 00:04:19,140
So that's why we cannot do it simply in this manner.

91
00:04:19,140 --> 00:04:24,840
But we have to recursively call the same function with which we created the node to go ahead and process

92
00:04:24,840 --> 00:04:26,100
the other nodes as well.

93
00:04:26,100 --> 00:04:29,040
So let's go ahead and take a look at how we proceed with this.

94
00:04:29,040 --> 00:04:32,580
And the best way to understand this is by just walking through it.

95
00:04:32,580 --> 00:04:37,770
So let's try to see how we go about with this now because this is going to be a recursive solution.

96
00:04:37,770 --> 00:04:39,480
Let's keep track of the call stack.

97
00:04:39,480 --> 00:04:46,950
So this particular call where we created the node with value five was when we passed left to be equal

98
00:04:46,950 --> 00:04:49,080
to zero and right to be equal to eight.

99
00:04:49,080 --> 00:04:50,820
So let's write that in our call stack.

100
00:04:50,820 --> 00:04:51,840
So we have zero eight.

101
00:04:51,840 --> 00:04:54,030
So left is zero and right is eight.

102
00:04:54,030 --> 00:04:57,360
And with this call we identified the middle as five.

103
00:04:57,360 --> 00:04:59,280
And that was made to a node.

104
00:04:59,280 --> 00:04:59,940
So that is where.

105
00:05:00,070 --> 00:05:05,260
We are at now, we are going to see how we will recursively call the same function towards the left

106
00:05:05,260 --> 00:05:07,870
part, which is this part and the right part.

107
00:05:08,510 --> 00:05:09,890
All right, so let's proceed.

108
00:05:09,920 --> 00:05:12,230
Now first we will go with the left.

109
00:05:12,230 --> 00:05:13,820
So that is this section over here.

110
00:05:13,820 --> 00:05:18,230
So you can see that the left extreme over here is zero itself.

111
00:05:18,230 --> 00:05:22,430
And the right is middle minus one which is four minus one which is three.

112
00:05:22,430 --> 00:05:24,860
So we are going to make a call to the same function.

113
00:05:24,860 --> 00:05:26,450
And left is going to be zero.

114
00:05:26,450 --> 00:05:27,830
And right is going to be three.

115
00:05:27,830 --> 00:05:29,780
So let's write that in our call stack.

116
00:05:29,780 --> 00:05:31,580
So we have zero comma three over here.

117
00:05:31,580 --> 00:05:33,500
And once we are out of this right.

118
00:05:33,500 --> 00:05:35,900
Once we are out of this we will process the right.

119
00:05:35,900 --> 00:05:41,000
So that's going to be a call where left is going to be middle plus one which is five and right is going

120
00:05:41,000 --> 00:05:43,610
to be eight itself, which is this part over here right now.

121
00:05:43,610 --> 00:05:45,980
Let me just write this over here as a placeholder.

122
00:05:45,980 --> 00:05:52,040
So once we go deep and once we come back, right, once this processing is over, we will go ahead and

123
00:05:52,040 --> 00:05:57,260
process the right, which is calling the same function by passing left as five and right as eight.

124
00:05:57,260 --> 00:05:58,250
So let's proceed.

125
00:05:58,250 --> 00:06:01,700
Now we are in this call where left is zero and right is three.

126
00:06:01,700 --> 00:06:06,290
Again we calculate middle as floor of zero plus three by two, which is equal to one.

127
00:06:06,290 --> 00:06:09,290
So at index one we have the element two.

128
00:06:09,290 --> 00:06:11,240
And this was part of the left call right.

129
00:06:11,240 --> 00:06:12,710
So this was part of the left call.

130
00:06:12,710 --> 00:06:18,530
So that's why this this value over here is going to be made a node and made the left of this particular

131
00:06:18,530 --> 00:06:19,070
node.

132
00:06:19,400 --> 00:06:19,670
All right.

133
00:06:19,670 --> 00:06:20,600
So we have two over here.

134
00:06:20,600 --> 00:06:25,910
And that's the left of this particular node again that we we know that this is going to be left of this

135
00:06:25,910 --> 00:06:28,370
node because this was part of the left call.

136
00:06:28,370 --> 00:06:29,030
Right.

137
00:06:29,510 --> 00:06:30,290
So let's proceed.

138
00:06:30,290 --> 00:06:33,740
And we know everything to the left of something is going to be less than that value.

139
00:06:33,740 --> 00:06:36,290
Because the array which is given to us is sorted.

140
00:06:36,290 --> 00:06:37,190
So let's proceed.

141
00:06:37,190 --> 00:06:38,540
So we are done this much.

142
00:06:38,540 --> 00:06:41,480
Now again a side note quick side note over here.

143
00:06:41,480 --> 00:06:45,800
We could ideally just go ahead and identify that we have to insert two next.

144
00:06:45,800 --> 00:06:50,960
And then we can just call the insert function for the binary search tree which is an instance method.

145
00:06:50,960 --> 00:06:51,140
Right.

146
00:06:51,140 --> 00:06:53,720
Which we have previously written in a previous question.

147
00:06:53,720 --> 00:06:54,920
So we could do that.

148
00:06:54,920 --> 00:07:00,980
But that would be a O of log n operation, because we know that inserting into a binary search tree

149
00:07:00,980 --> 00:07:02,840
is a o of log n operation.

150
00:07:02,840 --> 00:07:08,120
So this is not efficient because we could do it just in constant time, which is a O of one operation,

151
00:07:08,120 --> 00:07:13,280
because we know that this has to be the left of this particular node, because this was called on the

152
00:07:13,280 --> 00:07:13,850
left part.

153
00:07:13,850 --> 00:07:14,120
Right.

154
00:07:14,120 --> 00:07:17,330
So this was the left call of the same recursive function.

155
00:07:17,330 --> 00:07:18,920
So we know that we are over here.

156
00:07:18,920 --> 00:07:22,640
Hence we can just make it manually the left of this particular node.

157
00:07:22,640 --> 00:07:28,730
So that is going to be an O of one operation O of one time operation, which is more efficient.

158
00:07:28,730 --> 00:07:30,530
That's why we are proceeding in this manner.

159
00:07:30,530 --> 00:07:32,510
So let's go ahead and continue.

160
00:07:33,690 --> 00:07:39,600
So we have five over here, and we have identified that two is going to be towards the left of five.

161
00:07:39,600 --> 00:07:41,730
And that was part of this call zero three.

162
00:07:41,730 --> 00:07:42,030
Right.

163
00:07:42,030 --> 00:07:43,020
So let's proceed.

164
00:07:43,020 --> 00:07:47,220
Now we are inside this call where we are having left as zero and right as three.

165
00:07:47,220 --> 00:07:50,730
So we made a node and now we are going to process its left.

166
00:07:50,730 --> 00:07:51,990
So this is the middle now right.

167
00:07:51,990 --> 00:07:53,520
So this is the middle right.

168
00:07:53,520 --> 00:07:54,600
So let me just write this over here.

169
00:07:54,600 --> 00:07:55,320
This is the middle.

170
00:07:55,320 --> 00:07:57,330
Now its left is going to be this part.

171
00:07:57,330 --> 00:07:59,430
And its right is going to be this part.

172
00:07:59,430 --> 00:08:00,270
So let's write that.

173
00:08:00,270 --> 00:08:03,570
So we are going to make a call on the left where middle is this part.

174
00:08:03,570 --> 00:08:09,660
So the left part at this point have has left as zero and right as middle minus one which is one, minus

175
00:08:09,660 --> 00:08:11,130
one which is zero itself.

176
00:08:11,130 --> 00:08:14,460
So left is going to be zero, and right also is going to be zero.

177
00:08:14,460 --> 00:08:18,390
So we are going to have a call again for the same function with zero comma zero.

178
00:08:18,390 --> 00:08:18,840
All right.

179
00:08:18,840 --> 00:08:21,990
So at this point middle is again going to be calculated.

180
00:08:21,990 --> 00:08:26,220
So when we calculate middle and let me just have a placeholder over here.

181
00:08:26,220 --> 00:08:30,360
After we are done with the left part we are going to process the right part which is two comma three

182
00:08:30,360 --> 00:08:30,540
right.

183
00:08:30,540 --> 00:08:33,030
So left is going to be middle plus one which is two.

184
00:08:33,030 --> 00:08:34,530
And right remains unchanged.

185
00:08:34,530 --> 00:08:36,690
So let's write that over here which is two comma three.

186
00:08:36,690 --> 00:08:37,860
So let's go ahead.

187
00:08:37,860 --> 00:08:44,100
Now when we process the call with zero comma zero left and right both are going to point at index zero

188
00:08:44,100 --> 00:08:44,340
right.

189
00:08:44,340 --> 00:08:51,690
So left and right points at index zero and middle in that case is going to be also pointing at index

190
00:08:51,690 --> 00:08:53,700
zero because left is pointing over here.

191
00:08:53,700 --> 00:08:54,870
Right is also pointing over here.

192
00:08:54,870 --> 00:08:57,900
So middle will be zero plus zero by two which is zero itself.

193
00:08:57,900 --> 00:08:58,170
Right.

194
00:08:58,170 --> 00:09:01,650
So we are getting this value one over here at the index middle.

195
00:09:01,650 --> 00:09:06,990
So we are going to make a node out of it and insert it to the left of this particular node.

196
00:09:06,990 --> 00:09:11,190
So we know that it's the left of this node because this was part of the left call.

197
00:09:11,190 --> 00:09:11,370
Right.

198
00:09:11,370 --> 00:09:12,420
This was the left call.

199
00:09:12,420 --> 00:09:14,460
This is going to be the right call right.

200
00:09:14,460 --> 00:09:15,720
So this again was the left call.

201
00:09:15,720 --> 00:09:18,240
That's why we got this towards the left of this node.

202
00:09:18,240 --> 00:09:19,680
And this is the right call.

203
00:09:20,340 --> 00:09:20,610
All right.

204
00:09:20,610 --> 00:09:22,200
So let's proceed now.

205
00:09:22,200 --> 00:09:23,160
Middle is over here.

206
00:09:23,160 --> 00:09:24,210
Middle is over here right.

207
00:09:24,210 --> 00:09:26,400
So middle is at index zero.

208
00:09:26,400 --> 00:09:29,880
Now we are going to process its left and then its right.

209
00:09:29,880 --> 00:09:31,470
We can see both are empty right.

210
00:09:31,470 --> 00:09:34,020
So we're going to just just get null and null over here.

211
00:09:34,020 --> 00:09:35,010
Let's see why.

212
00:09:35,040 --> 00:09:40,380
So again when we process its left all we're doing is we are keeping left as it is, which is zero.

213
00:09:40,380 --> 00:09:43,710
And right is going to be middle minus one which is zero minus one.

214
00:09:43,710 --> 00:09:47,430
So we are making a call with left as zero and right as minus one.

215
00:09:47,430 --> 00:09:50,880
And this will be the base case of the recursive call.

216
00:09:50,880 --> 00:09:54,780
That is, when left is greater than right we will just return null.

217
00:09:54,780 --> 00:09:56,160
So that's going to be the base case.

218
00:09:56,160 --> 00:09:57,810
So we hit the base case over here.

219
00:09:57,810 --> 00:09:59,820
And this is just going to return null.

220
00:09:59,820 --> 00:10:00,330
All right.

221
00:10:00,330 --> 00:10:05,220
So that's how we get null as the left of this particular node over here.

222
00:10:05,220 --> 00:10:07,080
Then we are going to process the right.

223
00:10:07,080 --> 00:10:07,410
All right.

224
00:10:07,410 --> 00:10:09,270
So this was the left of this.

225
00:10:09,270 --> 00:10:11,550
Now again we are going to process its right.

226
00:10:11,550 --> 00:10:14,670
So for this again we are going to leave right as it is.

227
00:10:14,670 --> 00:10:19,650
And left is just going to be middle plus one which is going to be zero plus one because middle was zero.

228
00:10:19,650 --> 00:10:22,050
So we are having a call with one comma zero.

229
00:10:22,050 --> 00:10:23,280
That's the right call.

230
00:10:23,280 --> 00:10:27,120
And that also is going to return because you can see left is greater than right.

231
00:10:27,120 --> 00:10:28,260
And that's our base case.

232
00:10:28,260 --> 00:10:29,490
So this will also return.

233
00:10:29,490 --> 00:10:31,770
So over here also we get null.

234
00:10:32,430 --> 00:10:32,820
All right.

235
00:10:32,820 --> 00:10:33,930
So let's proceed.

236
00:10:33,930 --> 00:10:35,550
Now we are done with this call.

237
00:10:35,550 --> 00:10:37,530
So this now is going to be over.

238
00:10:37,530 --> 00:10:40,500
This call is going to be over because we identified the node.

239
00:10:40,500 --> 00:10:42,990
And then we did the left call and the right call.

240
00:10:42,990 --> 00:10:43,740
And that's over.

241
00:10:43,740 --> 00:10:43,890
Right.

242
00:10:43,890 --> 00:10:45,300
So this is going to return.

243
00:10:45,300 --> 00:10:47,490
Now we are going to have the right call.

244
00:10:47,490 --> 00:10:49,140
So we are going to have the right call.

245
00:10:49,140 --> 00:10:54,090
Now when we have the right call for this particular node we are going to use the indexes two and three.

246
00:10:54,090 --> 00:10:55,980
So we have already seen the logic for that right.

247
00:10:55,980 --> 00:10:58,710
So left is two and right is going to be three.

248
00:10:58,710 --> 00:11:00,900
That is we are leaving right as it is.

249
00:11:00,900 --> 00:11:03,120
And then we are changing left to middle plus one.

250
00:11:03,120 --> 00:11:04,890
And middle was one at that instance.

251
00:11:04,890 --> 00:11:06,930
So that's how we are getting two comma three.

252
00:11:06,930 --> 00:11:10,980
And again we calculate the new middle value which is going to be two plus three by two.

253
00:11:10,980 --> 00:11:12,090
And then we will floor it.

254
00:11:12,090 --> 00:11:14,730
So we'll get two as the middle value at this instance.

255
00:11:14,730 --> 00:11:17,070
So at index two we have this value.

256
00:11:17,070 --> 00:11:18,210
So we make it a node.

257
00:11:18,210 --> 00:11:21,390
And we're going to insert it to the right because this was a right call.

258
00:11:21,390 --> 00:11:21,570
Right.

259
00:11:21,570 --> 00:11:23,550
So we know that it's going to be the right.

260
00:11:23,550 --> 00:11:27,150
So that's it again we proceed and we're going to check its left.

261
00:11:27,150 --> 00:11:31,500
And its right now for its left we see we don't have anything right.

262
00:11:31,500 --> 00:11:35,820
So its if the middle value at this point is two now left for its left.

263
00:11:35,820 --> 00:11:39,330
We are just going to change right to middle minus one which is one.

264
00:11:39,330 --> 00:11:44,400
So we're going to have a call where two comma one left is two and right is one, right is one because

265
00:11:44,400 --> 00:11:45,510
that's two minus one.

266
00:11:45,510 --> 00:11:50,070
Again this will just return null because you can see left is greater than right.

267
00:11:50,070 --> 00:11:53,760
So that's why over here we are getting null and we proceed.

268
00:11:53,760 --> 00:11:55,200
We are making the right call.

269
00:11:55,200 --> 00:11:59,190
And for the right call what is what is the case that we are dealing with.

270
00:11:59,220 --> 00:12:00,660
You can see we have four over here.

271
00:12:00,660 --> 00:12:03,090
That is we are making a call with three comma three.

272
00:12:03,090 --> 00:12:03,390
Right.

273
00:12:03,390 --> 00:12:05,400
So we are leaving three as it is.

274
00:12:05,400 --> 00:12:08,550
And left is changed to right middle plus one.

275
00:12:08,550 --> 00:12:10,500
So middle is two two plus one is three.

276
00:12:10,500 --> 00:12:12,660
So at this case left is also three.

277
00:12:12,660 --> 00:12:13,680
Right is also three.

278
00:12:13,680 --> 00:12:18,240
And then we find middle is three plus three by two which is three itself.

279
00:12:18,240 --> 00:12:20,010
And that gives us this value over here.

280
00:12:20,010 --> 00:12:21,660
So we make a node out of it.

281
00:12:21,660 --> 00:12:24,960
And we are inserting it to the right of this particular node.

282
00:12:24,960 --> 00:12:26,280
Now we again proceed.

283
00:12:26,280 --> 00:12:28,590
We are going to check its left and its right.

284
00:12:28,590 --> 00:12:30,870
Now that's just going to be null and null again.

285
00:12:30,870 --> 00:12:31,140
Right.

286
00:12:31,290 --> 00:12:33,150
Because we will see that left is greater than.

287
00:12:33,620 --> 00:12:35,840
So it will return and we'll get null and null again.

288
00:12:35,840 --> 00:12:37,730
So this part over here is going to return.

289
00:12:37,730 --> 00:12:39,110
And then this is over.

290
00:12:39,110 --> 00:12:40,640
So that was part of the left call.

291
00:12:40,640 --> 00:12:41,000
All right.

292
00:12:41,000 --> 00:12:43,970
So this was part of the left call for this particular node.

293
00:12:43,970 --> 00:12:46,640
Now we are going to go ahead and process the right part.

294
00:12:46,640 --> 00:12:48,170
So let's just clear this up.

295
00:12:48,170 --> 00:12:49,940
So this part over here is done.

296
00:12:49,940 --> 00:12:51,860
Now we are making the right call.

297
00:12:51,860 --> 00:12:54,020
So let's just write it inside the call stack.

298
00:12:54,020 --> 00:12:56,480
So the left now is going to be five.

299
00:12:56,480 --> 00:12:59,120
And the right is going to point at index eight.

300
00:12:59,120 --> 00:13:02,540
We calculate the new middle which is five plus eight divided by two.

301
00:13:02,570 --> 00:13:05,660
So that's equal to 13 by two which is 6.5.

302
00:13:05,660 --> 00:13:08,120
And when we floor it that's going to be equal to six.

303
00:13:08,120 --> 00:13:10,040
So middle is pointing at index six.

304
00:13:10,040 --> 00:13:12,830
So we are going to make a node out of this.

305
00:13:12,830 --> 00:13:15,860
And this is going to be inserted towards the right of this node.

306
00:13:15,860 --> 00:13:18,740
And we know that it's towards the right because this is a right call.

307
00:13:18,740 --> 00:13:19,010
Right.

308
00:13:19,010 --> 00:13:20,450
So this was the right call.

309
00:13:20,450 --> 00:13:20,750
Right.

310
00:13:20,750 --> 00:13:22,370
So we're going to insert this over here.

311
00:13:22,370 --> 00:13:25,070
And then we proceed in the similar manner.

312
00:13:25,070 --> 00:13:27,860
Again we are going to call the same function.

313
00:13:27,860 --> 00:13:30,920
And we are going to process the left of the part left part.

314
00:13:30,920 --> 00:13:33,470
And this is the left part which is five comma five.

315
00:13:33,470 --> 00:13:35,660
And this is the right part which is eight comma nine.

316
00:13:35,660 --> 00:13:35,960
Right.

317
00:13:35,960 --> 00:13:37,310
So let's write that.

318
00:13:37,310 --> 00:13:40,040
Let's just write that over here seven comma eight okay.

319
00:13:40,040 --> 00:13:41,420
It's eight and nine are the values.

320
00:13:41,420 --> 00:13:43,070
But the indices are seven and eight.

321
00:13:43,070 --> 00:13:45,740
So the left call will have five comma five.

322
00:13:45,740 --> 00:13:47,180
That is left is left.

323
00:13:47,420 --> 00:13:49,010
Uh we are not changing the left index.

324
00:13:49,010 --> 00:13:52,160
And right is going to be middle minus one which is six minus one.

325
00:13:52,160 --> 00:13:53,420
That's how we get five over here.

326
00:13:53,420 --> 00:13:56,540
Now when we have five comma five that's the left call.

327
00:13:56,540 --> 00:13:59,510
Again middle is going to be equal to index five which is six.

328
00:13:59,510 --> 00:14:00,920
So we make a node out of this.

329
00:14:00,920 --> 00:14:03,680
And this is going to be inserted towards the left over here.

330
00:14:03,680 --> 00:14:06,680
And then we process the right part where we have seven and eight.

331
00:14:06,680 --> 00:14:11,510
So at that point middle is going to point towards index seven because seven plus eight by two.

332
00:14:11,510 --> 00:14:13,640
And then when we floor it we'll get seven itself.

333
00:14:13,640 --> 00:14:15,170
So this is the right call.

334
00:14:15,170 --> 00:14:19,790
So that's why this node over here which is eight is going to be inserted towards the right over here.

335
00:14:19,790 --> 00:14:21,170
So we have eight over here.

336
00:14:21,170 --> 00:14:23,840
And then we are going to process the left and right of this right.

337
00:14:23,840 --> 00:14:28,100
So in the left we're just going to return null because you can see we have nothing right.

338
00:14:28,100 --> 00:14:29,150
So there is nothing over here.

339
00:14:29,150 --> 00:14:30,740
So the left is going to be null.

340
00:14:31,780 --> 00:14:36,250
And again you can see that we are getting nulled because left is going to be greater than right at this

341
00:14:36,250 --> 00:14:38,050
point when we process it's left.

342
00:14:38,050 --> 00:14:42,190
So middle is seven, and when we process it's left we don't change the left.

343
00:14:42,190 --> 00:14:46,780
So left is seven itself and right is going to be middle minus one which is seven minus one which is

344
00:14:46,780 --> 00:14:47,170
six.

345
00:14:47,170 --> 00:14:50,200
So that's why you can see left is greater than right.

346
00:14:50,200 --> 00:14:51,370
And it will return null.

347
00:14:51,370 --> 00:14:52,840
So that's how we get null over here.

348
00:14:52,840 --> 00:14:56,350
And then when we process its right left is going to be eight.

349
00:14:56,350 --> 00:14:59,260
And right is going to be also eight right index eight.

350
00:14:59,260 --> 00:15:01,120
So we have a call with eight comma eight.

351
00:15:01,120 --> 00:15:04,060
So at this time we get middle also to be index eight.

352
00:15:04,060 --> 00:15:06,160
And that's pointing to the value nine.

353
00:15:06,160 --> 00:15:08,110
So we make a node out of this.

354
00:15:08,110 --> 00:15:10,660
And this is going to be inserted towards the right over here.

355
00:15:10,660 --> 00:15:12,700
And that's how we get nine over here.

356
00:15:12,700 --> 00:15:16,510
So this is how we are going to solve this question in the recursive manner.

357
00:15:16,510 --> 00:15:20,350
So let's just write this binary search tree in a neat manner over here.

358
00:15:20,350 --> 00:15:24,160
So we have five then 2134768 and nine.

359
00:15:24,160 --> 00:15:26,080
Now you can see that this is height balanced.

360
00:15:26,080 --> 00:15:28,540
This binary search tree over here is height balanced.

361
00:15:28,540 --> 00:15:30,490
So you can see for any subtree.

362
00:15:30,490 --> 00:15:36,130
For example for this one the difference between the depth of the nodes right is not greater than one

363
00:15:36,130 --> 00:15:36,340
right.

364
00:15:36,340 --> 00:15:39,070
So these are this is a height balanced binary search tree.

365
00:15:39,100 --> 00:15:42,100
Now let's also take a quick side note.

366
00:15:42,100 --> 00:15:48,010
This algorithm would not have worked if in the question it was not mentioned that the values in the

367
00:15:48,010 --> 00:15:49,750
array is strictly increasing.

368
00:15:49,750 --> 00:15:50,020
Right.

369
00:15:50,020 --> 00:15:55,480
So that's an interesting thing to notice about this algorithm, because it's given that the values are

370
00:15:55,480 --> 00:15:56,380
strictly increasing.

371
00:15:56,380 --> 00:15:58,600
That's why we know that the values are distinct.

372
00:15:58,600 --> 00:16:02,320
Now if they were not distinct then the algorithm would not work.

373
00:16:02,320 --> 00:16:03,430
Let's take an example.

374
00:16:03,430 --> 00:16:06,400
Let's say the array was one, two, two, two and three.

375
00:16:06,400 --> 00:16:10,840
Now in this case we would have found the middle as 01234.

376
00:16:10,870 --> 00:16:12,220
The middle would be index two.

377
00:16:12,220 --> 00:16:12,550
Right.

378
00:16:12,550 --> 00:16:15,160
So we go ahead and make a node out of this.

379
00:16:15,640 --> 00:16:20,080
And then when we process the left you can see that this value over here is two itself.

380
00:16:20,080 --> 00:16:20,350
Right.

381
00:16:20,350 --> 00:16:22,270
And this should not come to the left.

382
00:16:22,270 --> 00:16:26,230
It won't be part of the left subtree of this particular root node.

383
00:16:26,230 --> 00:16:29,260
So that is one reason why this is not going to be correct.

384
00:16:29,260 --> 00:16:30,940
Our algorithm is not going to work.

385
00:16:30,940 --> 00:16:34,420
And then you can see even if we insert all of these towards the right right.

386
00:16:34,420 --> 00:16:36,250
It's not going to be height balanced.

387
00:16:36,250 --> 00:16:39,310
You can have two and two over here and three over here and one over here.

388
00:16:39,310 --> 00:16:41,650
So that it follows the binary search tree property.

389
00:16:41,650 --> 00:16:43,420
But this is not going to be height balanced.

390
00:16:43,420 --> 00:16:46,510
So the algorithm will not work if the values are not distinct.

391
00:16:46,510 --> 00:16:48,550
So this is a good observation to make.

392
00:16:48,550 --> 00:16:52,480
Now let's proceed and take a look at the time and space complexity of this solution.

393
00:16:52,480 --> 00:16:57,460
Now the time complexity of this solution is going to be O of n, because we have to traverse through

394
00:16:57,460 --> 00:17:01,480
each element of the given array, and then we have to make a node out of it.

395
00:17:01,480 --> 00:17:01,750
Right.

396
00:17:01,750 --> 00:17:03,640
So we have to make a node out of it.

397
00:17:03,640 --> 00:17:09,280
And then we have to uh, go ahead and recursively call the same function for its left and its, its

398
00:17:09,280 --> 00:17:11,710
particular right of the particular node where we are at.

399
00:17:11,710 --> 00:17:17,860
So you can see we have to traverse through the elements, we have to make a node and at every element.

400
00:17:17,860 --> 00:17:23,260
So basically you can think of it in this manner every element has to become the middle at some point

401
00:17:23,260 --> 00:17:26,590
so that we can make a node out of it and insert it into a binary search tree.

402
00:17:26,590 --> 00:17:32,860
So the time complexity over here is going to be O of n, and the space complexity is also going to be

403
00:17:32,860 --> 00:17:33,490
O of n.

404
00:17:33,490 --> 00:17:34,030
Why is that.

405
00:17:34,030 --> 00:17:37,120
So that so now what are the things that take up space.

406
00:17:37,120 --> 00:17:39,520
We will have to return the binary search tree.

407
00:17:39,520 --> 00:17:42,400
And then we will also take up space on the call stack.

408
00:17:42,400 --> 00:17:45,430
Now the binary search tree is going to have n elements.

409
00:17:45,430 --> 00:17:49,870
So that's why the space of this binary search tree is going to be of the order of n.

410
00:17:49,870 --> 00:17:55,420
But when it comes to the call stack we are going to have only calls, which is of the order of the height

411
00:17:55,420 --> 00:17:56,560
of the binary search tree.

412
00:17:56,560 --> 00:17:56,830
Right.

413
00:17:56,830 --> 00:18:03,250
So we can say that the space used because of the call stack is going to be O of log n or O of the height

414
00:18:03,250 --> 00:18:04,510
of the binary search tree.

415
00:18:04,510 --> 00:18:08,920
Now, because this is a balanced, uh, height balanced binary binary search tree, we can say that

416
00:18:08,920 --> 00:18:11,050
the height is going to be of the order of log n.

417
00:18:11,050 --> 00:18:15,580
So the space taken up by the call stack is going to be of the order of log n.

418
00:18:15,580 --> 00:18:17,350
But because this is greater than this.

419
00:18:17,350 --> 00:18:21,490
So we can say that the space complexity of this solution is going to be o of n.