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

2
00:00:01,520 --> 00:00:07,670
Let's now go ahead and code the recursive solution, which we discussed in the previous video, where

3
00:00:07,670 --> 00:00:11,030
we are given a sorted array which is strictly increasing.

4
00:00:11,030 --> 00:00:14,960
And from this array we will create a binary search tree which is height balanced.

5
00:00:14,960 --> 00:00:16,610
So let's go ahead and do this.

6
00:00:16,610 --> 00:00:19,400
Now to start with I'm going to have a class node.

7
00:00:19,400 --> 00:00:22,460
So using this class we will create each node.

8
00:00:22,460 --> 00:00:24,620
And we'll have our constructor over here.

9
00:00:25,010 --> 00:00:28,280
And to the constructor we will be passing the value.

10
00:00:29,040 --> 00:00:34,200
And then inside over here we're just going to say this dot value is equal to the value which is passed

11
00:00:34,200 --> 00:00:34,890
over here.

12
00:00:35,580 --> 00:00:39,630
And we will say this dot left is equal to null.

13
00:00:39,960 --> 00:00:43,230
And this dot right is equal to null.

14
00:00:43,230 --> 00:00:46,920
So each node is going to have a value and a left and a right.

15
00:00:46,920 --> 00:00:47,430
All right.

16
00:00:47,460 --> 00:00:49,770
Now let's go ahead and write the function.

17
00:00:49,770 --> 00:00:52,740
So let's call this function build BST.

18
00:00:55,580 --> 00:00:57,890
From sorted array.

19
00:00:59,860 --> 00:01:00,370
All right.

20
00:01:00,400 --> 00:01:03,370
Now this function is going to take in the array.

21
00:01:03,370 --> 00:01:05,200
So let's just call this array numb's.

22
00:01:05,200 --> 00:01:08,110
And it's also going to take in the left index.

23
00:01:08,110 --> 00:01:11,170
And the right index where we are at that particular instance.

24
00:01:11,290 --> 00:01:13,480
That's because this is going to be a recursive function right.

25
00:01:13,480 --> 00:01:18,970
So inside this function we will call this function again by varying the left and the right pointers.

26
00:01:18,970 --> 00:01:21,460
So left initially is going to be equal to zero.

27
00:01:21,460 --> 00:01:26,290
And right initially is going to be equal to numb's dot length minus one.

28
00:01:27,310 --> 00:01:30,850
Now inside this function first let's write the base case.

29
00:01:31,150 --> 00:01:35,170
So the base case is going to be when left is greater than right right.

30
00:01:35,170 --> 00:01:38,170
So if left is greater than right.

31
00:01:38,710 --> 00:01:41,110
In that case we can just return null.

32
00:01:42,530 --> 00:01:45,500
So when this hits, we will be returning null.

33
00:01:45,500 --> 00:01:48,410
So that place is going to be a null in the binary search tree.

34
00:01:48,440 --> 00:01:48,980
All right.

35
00:01:49,010 --> 00:01:50,090
Now let's proceed.

36
00:01:50,120 --> 00:01:54,650
Now we go ahead and calculate middle in the array which is given to us which is numb's over here.

37
00:01:54,650 --> 00:01:59,690
So let's say let middle is equal to math dot floor.

38
00:02:01,520 --> 00:02:04,520
Left plus right divided by two.

39
00:02:07,330 --> 00:02:13,180
And after identifying the middle value in the array at that particular call, we are going to create

40
00:02:13,180 --> 00:02:14,620
a node out of this value.

41
00:02:14,620 --> 00:02:19,120
So let's say const node is equal to new node.

42
00:02:19,120 --> 00:02:21,550
So we are calling the constructor over here.

43
00:02:21,550 --> 00:02:27,370
And then we will be passing this value which is the middle in the value at the index middle in the array

44
00:02:27,370 --> 00:02:28,150
which is given to us.

45
00:02:28,150 --> 00:02:30,970
So over here we are passing numb's at middle.

46
00:02:32,260 --> 00:02:34,810
So using this value we create a node.

47
00:02:34,810 --> 00:02:40,450
And then we are just going to go ahead and recursively call the same function to identify the left and

48
00:02:40,450 --> 00:02:42,700
right positions for this particular node.

49
00:02:42,700 --> 00:02:46,060
So we can say node dot left is equal to.

50
00:02:46,090 --> 00:02:49,300
Again we call the same function build BST from sorted array.

51
00:02:49,300 --> 00:02:51,070
And now we pass the array.

52
00:02:51,070 --> 00:02:54,310
And because this is the left right this is node dot left.

53
00:02:54,310 --> 00:02:55,870
So we don't change left.

54
00:02:55,870 --> 00:02:57,340
Left is going to be as it is.

55
00:02:57,340 --> 00:03:00,370
But right is going to be changed to middle minus one.

56
00:03:02,380 --> 00:03:02,890
All right.

57
00:03:02,920 --> 00:03:05,920
Now we're going to do the same thing for node dot right as well.

58
00:03:05,920 --> 00:03:10,390
So node dot right is going to be the same function we call the function recursively.

59
00:03:10,390 --> 00:03:14,890
And now because we are trying to find the right position.

60
00:03:14,890 --> 00:03:17,380
So we're going to change left to middle plus one.

61
00:03:17,410 --> 00:03:19,270
So this is going to be middle plus one.

62
00:03:19,270 --> 00:03:21,580
And then right is not changing at all.

63
00:03:21,580 --> 00:03:22,990
It's going to be right itself.

64
00:03:24,050 --> 00:03:24,470
All right.

65
00:03:24,470 --> 00:03:25,430
So that's it.

66
00:03:25,430 --> 00:03:30,560
And then this will keep recursively calling the function till it hits the base case at which point it

67
00:03:30,560 --> 00:03:31,520
will return null.

68
00:03:31,550 --> 00:03:36,740
So finally after we are done with this after these return we will just return the node.

69
00:03:38,000 --> 00:03:42,440
So that will be the head of the binary search, the root of the binary search tree.

70
00:03:42,470 --> 00:03:42,950
All right.

71
00:03:42,950 --> 00:03:46,460
So let's go ahead and call the function and test our code.

72
00:03:48,330 --> 00:03:50,340
And let's say we are passing an array.

73
00:03:50,340 --> 00:03:52,650
So one, two, three, four and five.

74
00:03:52,650 --> 00:03:55,020
So this is the sorted array which is passed to it.

75
00:03:55,020 --> 00:03:56,730
So let's go ahead and call this function.

76
00:03:56,730 --> 00:03:58,620
And let's take a look at the output.

77
00:03:58,620 --> 00:04:00,090
So we are getting three over here.

78
00:04:00,090 --> 00:04:02,790
So let's try to draw the output so that we can visualize this.

79
00:04:02,790 --> 00:04:04,740
So let me just grab a pen.

80
00:04:05,550 --> 00:04:06,150
All right.

81
00:04:06,150 --> 00:04:11,580
So over here you can see that the binary search tree has three over here which is the root.

82
00:04:11,580 --> 00:04:11,820
Right.

83
00:04:11,820 --> 00:04:13,350
So let's write three over here.

84
00:04:13,980 --> 00:04:15,690
And let's open it up.

85
00:04:15,690 --> 00:04:20,220
So you can see after this the left of this node is one and the right is four.

86
00:04:20,220 --> 00:04:21,690
So let's write this over here.

87
00:04:21,690 --> 00:04:25,140
So the left over here is one and the right is node four.

88
00:04:25,140 --> 00:04:28,140
And then if we open this up let's open this also.

89
00:04:28,140 --> 00:04:31,800
So we get the left of this node over here is going to be null.

90
00:04:31,800 --> 00:04:33,270
So this is null.

91
00:04:34,590 --> 00:04:37,080
And the right is going to be a node with value two.

92
00:04:37,110 --> 00:04:38,340
So this is two over here.

93
00:04:38,370 --> 00:04:41,580
Now if we open this up it's just going to be null and null.

94
00:04:41,610 --> 00:04:41,940
All right.

95
00:04:41,940 --> 00:04:42,750
So that's correct.

96
00:04:42,780 --> 00:04:44,430
Now let's open this part as well.

97
00:04:44,430 --> 00:04:49,020
So four is having the left node as null and the right node as five.

98
00:04:49,020 --> 00:04:50,130
So this is null.

99
00:04:51,370 --> 00:04:52,870
And this is five.

100
00:04:52,870 --> 00:04:56,140
Now if we open up five, we will just get null and null.

101
00:04:56,620 --> 00:04:56,920
Yes.

102
00:04:56,920 --> 00:04:57,580
That's correct.

103
00:04:57,580 --> 00:05:00,280
So this is how the binary search tree looks like.

104
00:05:00,280 --> 00:05:05,320
So you can see yes, this is a binary search tree because the binary search tree property is fulfilled.

105
00:05:05,320 --> 00:05:07,960
So everything to the right of three is less than three.

106
00:05:07,960 --> 00:05:13,780
And everything sorry, everything to the left of three is less than three, and everything to the right

107
00:05:13,780 --> 00:05:15,490
of three is greater than three.

108
00:05:15,490 --> 00:05:18,130
So we can see that the binary search tree is fulfilled.

109
00:05:18,130 --> 00:05:20,440
And that's also true with each of these nodes.

110
00:05:20,440 --> 00:05:20,650
Right?

111
00:05:20,650 --> 00:05:23,260
So whatever is right of one is greater than one.

112
00:05:23,260 --> 00:05:25,930
Whatever is right of four is greater than four.

113
00:05:25,930 --> 00:05:28,420
So yes, this is how the binary search tree looks.

114
00:05:28,420 --> 00:05:30,460
And we can see that it is height balanced.

115
00:05:30,460 --> 00:05:30,790
Right.

116
00:05:30,790 --> 00:05:34,810
So the height of these two subtrees are the same.

117
00:05:34,810 --> 00:05:35,170
Right.

118
00:05:35,170 --> 00:05:38,920
And the height over here differs by one because this is over here null.

119
00:05:38,920 --> 00:05:40,420
And we have a node over here.

120
00:05:40,420 --> 00:05:42,970
So yes this is a height balanced binary search tree.

121
00:05:42,970 --> 00:05:44,170
And it's working.

122
00:05:44,170 --> 00:05:48,040
Now let's try to run through the code and understand how this is working.

123
00:05:48,040 --> 00:05:49,510
So we'll take the same input.

124
00:05:49,510 --> 00:05:51,820
So let's just clear this up over here.

125
00:05:53,690 --> 00:05:57,110
And the array which is passed to us is one, two, three, four, five.

126
00:05:57,110 --> 00:06:02,300
And we are calling the build binary search tree from sorted array function and left at this point is

127
00:06:02,300 --> 00:06:05,300
equal to zero and right is equal to the length minus one.

128
00:06:05,300 --> 00:06:06,470
The length over here is five.

129
00:06:06,470 --> 00:06:07,850
So right is equal to four.

130
00:06:07,850 --> 00:06:09,950
So let's track our call stack over here.

131
00:06:09,950 --> 00:06:12,890
So this is the call with zero and four.

132
00:06:13,810 --> 00:06:14,080
All right.

133
00:06:14,080 --> 00:06:16,240
So left is zero and right is four.

134
00:06:16,240 --> 00:06:19,150
Now let's go ahead and see what's happening over here.

135
00:06:19,150 --> 00:06:20,140
So left is zero.

136
00:06:20,140 --> 00:06:21,010
Right is four.

137
00:06:21,010 --> 00:06:23,260
And we see that left is not greater than right.

138
00:06:23,260 --> 00:06:25,660
So we continue and we are calculating middle.

139
00:06:25,660 --> 00:06:27,490
Middle is left plus right by two.

140
00:06:27,520 --> 00:06:29,500
So that's equal to two at this point.

141
00:06:29,500 --> 00:06:34,030
Now let's write the indices over here 0123 and four.

142
00:06:34,030 --> 00:06:34,480
All right.

143
00:06:34,480 --> 00:06:36,970
So at index two we have the value three.

144
00:06:36,970 --> 00:06:41,290
So we are going ahead and making a node with this value which is three.

145
00:06:41,290 --> 00:06:43,180
So let's write the node over here.

146
00:06:43,180 --> 00:06:45,040
So this is our node with value three.

147
00:06:45,040 --> 00:06:47,320
And then we are saying node dot left.

148
00:06:47,320 --> 00:06:52,780
That is whatever should come over here is what we get back from this function called over here.

149
00:06:52,780 --> 00:06:55,120
Now let's take a look at this function call over here.

150
00:06:55,720 --> 00:06:58,090
At this point left is not changing.

151
00:06:58,090 --> 00:07:01,600
So left is still zero and right is going to be middle minus one.

152
00:07:01,600 --> 00:07:02,710
And middle is equal to two.

153
00:07:02,740 --> 00:07:04,030
So right is equal to one.

154
00:07:04,030 --> 00:07:07,510
So we are making a call and the left index is zero.

155
00:07:07,510 --> 00:07:09,130
And the right index is one.

156
00:07:09,130 --> 00:07:09,400
All right.

157
00:07:09,400 --> 00:07:12,340
So this is the call for node dot left.

158
00:07:12,340 --> 00:07:15,730
Now let me just have a placeholder over here for node dot right.

159
00:07:15,730 --> 00:07:17,680
So when we call node dot right.

160
00:07:17,680 --> 00:07:19,390
When we try to find node dot right.

161
00:07:19,390 --> 00:07:21,160
That is whatever comes over here.

162
00:07:21,160 --> 00:07:26,230
We are going to pass the left index as middle plus one which is two plus one which is three.

163
00:07:26,230 --> 00:07:28,930
And right is not going to change which is four itself.

164
00:07:28,930 --> 00:07:29,320
All right.

165
00:07:29,320 --> 00:07:31,330
So let's have a placeholder for that.

166
00:07:31,330 --> 00:07:34,330
So that's going to be three comma four.

167
00:07:34,900 --> 00:07:36,190
So we'll come back to this.

168
00:07:36,190 --> 00:07:37,570
Now let's proceed.

169
00:07:37,960 --> 00:07:39,640
Now we are in the call zero one.

170
00:07:39,640 --> 00:07:41,920
So let's just clear this up a little bit.

171
00:07:42,640 --> 00:07:48,550
And we are again inside the build BSD from sorted array function, and we are trying to find out what

172
00:07:48,550 --> 00:07:49,570
should come over here.

173
00:07:49,570 --> 00:07:51,100
Now we are inside.

174
00:07:51,100 --> 00:07:53,890
This left is equal to zero and right is equal to one.

175
00:07:53,890 --> 00:07:55,360
Left is not greater than right.

176
00:07:55,360 --> 00:08:00,040
So we come over here and we calculate middle which is going to be zero plus one divided by two.

177
00:08:00,040 --> 00:08:01,420
And then we are floating it right.

178
00:08:01,420 --> 00:08:03,130
So that's going to be equal to zero.

179
00:08:03,130 --> 00:08:04,600
So middle is equal to zero.

180
00:08:04,600 --> 00:08:06,430
So that's this index over here.

181
00:08:06,430 --> 00:08:08,590
So we make a node out of this right.

182
00:08:08,590 --> 00:08:10,120
We make a node out of this.

183
00:08:10,120 --> 00:08:13,090
And that's going to be this node over here.

184
00:08:13,090 --> 00:08:13,450
Right.

185
00:08:13,450 --> 00:08:15,880
So this is going to be the node with value one.

186
00:08:15,880 --> 00:08:16,810
So that's this node.

187
00:08:16,810 --> 00:08:17,260
All right.

188
00:08:17,260 --> 00:08:21,580
And over here you can see that we are returning this particular node.

189
00:08:21,580 --> 00:08:21,880
Right.

190
00:08:21,880 --> 00:08:23,170
So we are returning this node.

191
00:08:23,170 --> 00:08:27,190
That means in this call it's going to return this node over here.

192
00:08:29,050 --> 00:08:29,380
All right.

193
00:08:29,380 --> 00:08:31,480
And we have seen that that was for this position.

194
00:08:31,480 --> 00:08:35,740
So when we get to this line we will fill this node to this place.

195
00:08:35,740 --> 00:08:41,710
But before we get to this we are going to start first to identify what is to be made to the left and

196
00:08:41,710 --> 00:08:43,030
right of this particular node.

197
00:08:43,030 --> 00:08:44,230
So let's go ahead and do that.

198
00:08:44,230 --> 00:08:49,000
So I'm just writing this over here so that we can keep track of the recursive call and how it works.

199
00:08:49,000 --> 00:08:50,080
So let's continue.

200
00:08:50,080 --> 00:08:52,690
So we have made a node out of this value which is one.

201
00:08:52,690 --> 00:08:57,910
And then we are calling node dot left to identify what should be to the left of this.

202
00:08:57,910 --> 00:09:02,860
So and then later we will call node dot right to identify what should be the to the right of this.

203
00:09:02,860 --> 00:09:03,850
So that's how this works.

204
00:09:03,850 --> 00:09:09,130
So for this call node dot left we are again leaving left as it is which is zero itself.

205
00:09:09,130 --> 00:09:11,650
And right is going to be middle minus one.

206
00:09:11,650 --> 00:09:13,390
And middle is equal to zero right.

207
00:09:13,390 --> 00:09:17,260
So right is going to be minus one zero minus one is minus one.

208
00:09:17,260 --> 00:09:19,540
So when we come inside that call right.

209
00:09:19,540 --> 00:09:20,380
So zero minus one.

210
00:09:20,380 --> 00:09:23,020
Let me just write this over here zero minus one.

211
00:09:23,020 --> 00:09:28,030
When we come inside that call left is going to be greater than right because zero is greater than minus

212
00:09:28,030 --> 00:09:28,210
one.

213
00:09:28,210 --> 00:09:29,620
So we are going to return null.

214
00:09:29,620 --> 00:09:32,560
So that means over here we are going to have null.

215
00:09:32,560 --> 00:09:33,610
And this returns.

216
00:09:33,610 --> 00:09:34,150
All right.

217
00:09:34,150 --> 00:09:37,960
So later we come to this part where we are going to call node dot right.

218
00:09:37,960 --> 00:09:39,640
To identify what should come over here.

219
00:09:39,640 --> 00:09:42,730
At this point we are going to make left middle plus one.

220
00:09:42,730 --> 00:09:43,840
And middle was zero right.

221
00:09:43,840 --> 00:09:45,010
So that's going to be one.

222
00:09:45,010 --> 00:09:47,410
And right is not going to change at all.

223
00:09:47,410 --> 00:09:48,940
So right is one itself.

224
00:09:48,940 --> 00:09:49,300
All right.

225
00:09:49,300 --> 00:09:53,110
So we have one and one and we are inside the call.

226
00:09:53,110 --> 00:09:54,820
So let's write that over here in our call stack.

227
00:09:54,820 --> 00:09:58,090
Again we have a call with one comma one at this point.

228
00:09:58,090 --> 00:10:02,080
And middle is going to be one plus one divided by two which is one itself.

229
00:10:02,230 --> 00:10:04,210
So let's just clear this up a little bit.

230
00:10:07,470 --> 00:10:11,130
All right, so we have one and one over here.

231
00:10:12,570 --> 00:10:17,670
And middle is going to be one, and we are going to make a note out of what is there at index one,

232
00:10:17,670 --> 00:10:18,540
which is two.

233
00:10:18,570 --> 00:10:19,080
All right.

234
00:10:19,080 --> 00:10:22,170
And that two is going to be returned at this point.

235
00:10:22,170 --> 00:10:25,560
So we are making the node with value two over here.

236
00:10:25,560 --> 00:10:26,820
And then it's going to be returned.

237
00:10:26,820 --> 00:10:28,200
So it's going to be positioned over here.

238
00:10:28,200 --> 00:10:28,710
Right.

239
00:10:29,130 --> 00:10:32,100
And you can see over here these two are going to return null right.

240
00:10:32,100 --> 00:10:32,940
Because why is that.

241
00:10:32,940 --> 00:10:35,790
So it's left and it's light right are going to be null.

242
00:10:35,790 --> 00:10:38,460
So this is null and this is null.

243
00:10:39,000 --> 00:10:39,630
Why is that so.

244
00:10:39,630 --> 00:10:42,810
Because left is going to be greater than right in these instances.

245
00:10:42,810 --> 00:10:44,850
So we have one and one at this point.

246
00:10:44,850 --> 00:10:46,770
Now left is left unchanged.

247
00:10:46,770 --> 00:10:49,500
And right is going to be middle minus one which is zero.

248
00:10:49,500 --> 00:10:50,760
So we have one comma zero.

249
00:10:50,760 --> 00:10:52,200
So left is greater than right.

250
00:10:52,200 --> 00:10:53,910
So this returns and we have null over here.

251
00:10:53,910 --> 00:10:56,760
Similarly over here we are going to increment left.

252
00:10:56,760 --> 00:11:00,000
So left is going to be middle plus one middle plus one.

253
00:11:00,000 --> 00:11:03,510
So left is going to be two and right is left as it is which is one itself.

254
00:11:03,510 --> 00:11:06,270
So again when we come inside the function two is greater than one.

255
00:11:06,270 --> 00:11:08,760
So that's why this part also is going to be null.

256
00:11:08,760 --> 00:11:10,050
So this is also null.

257
00:11:10,050 --> 00:11:10,800
This is also null.

258
00:11:10,800 --> 00:11:12,870
So this is this has been formed.

259
00:11:12,870 --> 00:11:17,010
And then we come over here and we have seen that that's what is going to happen over here.

260
00:11:17,010 --> 00:11:17,190
Right.

261
00:11:17,190 --> 00:11:18,090
We created one.

262
00:11:18,090 --> 00:11:21,870
And then we go deeper to identify its left and right.

263
00:11:21,870 --> 00:11:25,890
And at this point we again go deeper to identify its and its left and its right.

264
00:11:25,920 --> 00:11:27,480
Now these all have returned.

265
00:11:27,480 --> 00:11:32,730
So we come over here and now this node over here is going to return to this part.

266
00:11:32,730 --> 00:11:34,740
So we are going to place this over here.

267
00:11:34,740 --> 00:11:36,120
So one is coming over here.

268
00:11:36,120 --> 00:11:37,920
And this is already constructed right.

269
00:11:37,920 --> 00:11:39,060
So this is null.

270
00:11:40,170 --> 00:11:41,610
And over here we have two.

271
00:11:41,610 --> 00:11:43,230
And over here we have null.

272
00:11:43,590 --> 00:11:45,390
And over here we have null.

273
00:11:45,570 --> 00:11:46,110
All right.

274
00:11:46,110 --> 00:11:47,460
So this has returned.

275
00:11:47,460 --> 00:11:52,830
So this was this part right where we created the node one.

276
00:11:52,830 --> 00:11:53,340
All right.

277
00:11:53,340 --> 00:11:58,440
So that was part of this call where we passed zero as the left index and one as the right index.

278
00:11:58,440 --> 00:12:02,190
Now that was part of node dot left right the left of this index.

279
00:12:02,190 --> 00:12:03,960
So this part over here is done.

280
00:12:03,960 --> 00:12:05,520
Now we come to this line.

281
00:12:05,520 --> 00:12:07,110
Let me just change the color of the pen.

282
00:12:07,110 --> 00:12:09,720
We come over here and we identify node dot right.

283
00:12:09,720 --> 00:12:12,000
That is what is it that should come over here.

284
00:12:12,000 --> 00:12:14,430
And for this we are passing three comma four.

285
00:12:14,430 --> 00:12:16,290
So let's just clear this up a little bit.

286
00:12:18,510 --> 00:12:22,620
So left is passed as three and right is passed as four.

287
00:12:26,230 --> 00:12:26,560
All right.

288
00:12:26,560 --> 00:12:29,470
So left is three and right is four.

289
00:12:29,500 --> 00:12:30,940
Now we come over here.

290
00:12:30,940 --> 00:12:33,640
Left is is left greater than three for right.

291
00:12:33,640 --> 00:12:35,110
No three is not greater than four.

292
00:12:35,110 --> 00:12:40,540
So we continue and we go ahead and identify the middle value which is three plus four divided by two.

293
00:12:40,540 --> 00:12:41,560
And then we have flooring it.

294
00:12:41,560 --> 00:12:43,990
So we will get three itself as the middle value.

295
00:12:43,990 --> 00:12:45,070
And this is zero.

296
00:12:45,070 --> 00:12:47,800
This is one this is two this is three this is four.

297
00:12:47,800 --> 00:12:50,470
So at index three we have the value four.

298
00:12:50,470 --> 00:12:53,110
So we are going to make a node out of it right.

299
00:12:53,110 --> 00:12:55,630
So this is going to be node four.

300
00:12:56,080 --> 00:12:58,780
And then we will return this at this line.

301
00:12:58,780 --> 00:13:00,370
So it will come and sit over here.

302
00:13:00,370 --> 00:13:04,960
But before that we will identify its left and its right in these parts.

303
00:13:04,960 --> 00:13:05,830
So its left.

304
00:13:05,830 --> 00:13:06,940
Let's go ahead over here.

305
00:13:06,940 --> 00:13:08,260
Let's see what's happening over here.

306
00:13:08,260 --> 00:13:09,790
Let me just clear this up also.

307
00:13:09,790 --> 00:13:13,330
So in our call stack we just have this call which is three comma four.

308
00:13:16,130 --> 00:13:17,600
So let's write that over here.

309
00:13:19,350 --> 00:13:23,370
And we have seen that this will return the node four once it's back.

310
00:13:23,400 --> 00:13:23,820
All right.

311
00:13:23,820 --> 00:13:24,930
So we're going deeper.

312
00:13:24,930 --> 00:13:29,670
First we are calling node dot left to identify what should come in this place.

313
00:13:29,670 --> 00:13:31,710
And left is left as it is.

314
00:13:31,710 --> 00:13:32,970
So we have three itself.

315
00:13:32,970 --> 00:13:35,130
And right is going to be middle minus one.

316
00:13:35,130 --> 00:13:36,900
And middle is equal to three right.

317
00:13:36,900 --> 00:13:38,940
So middle minus one is going to be two.

318
00:13:38,940 --> 00:13:41,910
Now three comma two you can see left is greater than right.

319
00:13:41,910 --> 00:13:44,370
So it's going to return null when we come over here.

320
00:13:44,370 --> 00:13:44,520
Right.

321
00:13:44,520 --> 00:13:46,710
So left is greater than null greater than right.

322
00:13:46,710 --> 00:13:48,780
So this part over here is going to be null.

323
00:13:49,530 --> 00:13:49,800
All right.

324
00:13:49,800 --> 00:13:55,890
So then we continue we come to this line and we identify its right which is going to be again a recursive

325
00:13:55,890 --> 00:13:56,040
call.

326
00:13:56,040 --> 00:13:57,420
So this has returned null.

327
00:13:57,420 --> 00:13:58,650
So I'm just crossing it out.

328
00:13:58,650 --> 00:13:59,580
So we are over here.

329
00:13:59,580 --> 00:14:02,760
Now at this point we are calling the function again recursively.

330
00:14:02,760 --> 00:14:06,780
And left is going to be middle plus one which is three plus one which is four.

331
00:14:06,780 --> 00:14:09,360
And right is going to be right itself which is four.

332
00:14:09,360 --> 00:14:12,600
So we are calling the function recursively with four comma four.

333
00:14:12,600 --> 00:14:15,000
So we come over here four is not greater than four.

334
00:14:15,000 --> 00:14:17,760
So we continue and we are calculating the new middle.

335
00:14:17,760 --> 00:14:19,620
So at this point it's four comma four.

336
00:14:19,620 --> 00:14:21,090
So four plus four by two.

337
00:14:21,090 --> 00:14:22,440
That gives us four itself.

338
00:14:22,440 --> 00:14:24,930
And at index four we have the value five.

339
00:14:24,930 --> 00:14:27,360
So we are going to make a node out of this.

340
00:14:27,360 --> 00:14:28,890
And that's going to be placed over here.

341
00:14:28,890 --> 00:14:29,160
Right.

342
00:14:29,160 --> 00:14:30,570
So that is when it is returned.

343
00:14:30,570 --> 00:14:35,460
But again before that we identify its left and its right which is going to be null and null.

344
00:14:36,750 --> 00:14:37,020
Right?

345
00:14:37,020 --> 00:14:37,530
Why is that so?

346
00:14:37,530 --> 00:14:39,750
Because we have four and four at this moment.

347
00:14:39,750 --> 00:14:44,790
So when we call no dot left to identify what should come over here, left is going to be four, but

348
00:14:44,790 --> 00:14:47,100
right is going to be four minus one which is three.

349
00:14:47,100 --> 00:14:48,780
So you can see four is greater than three.

350
00:14:48,780 --> 00:14:50,790
So that's why it returns at this place.

351
00:14:50,790 --> 00:14:52,350
And hence we have null over here.

352
00:14:52,350 --> 00:14:57,660
Now when we come to no dot right we're going to pass middle plus one as left which is four plus one

353
00:14:57,660 --> 00:14:59,850
which is five and right is left as it is.

354
00:14:59,850 --> 00:15:04,920
So we have five and four again when we come inside over here we see that five is greater than four and

355
00:15:04,920 --> 00:15:05,700
it returns null.

356
00:15:05,700 --> 00:15:07,710
So this part over here is also null.

357
00:15:07,710 --> 00:15:11,700
So once this is done we're going to return this particular node which is five.

358
00:15:11,700 --> 00:15:16,950
And that is the right that was part of the node dot right called for this particular node.

359
00:15:16,950 --> 00:15:17,250
Right.

360
00:15:17,250 --> 00:15:18,150
So that's it.

361
00:15:18,150 --> 00:15:20,550
So this call over here will return.

362
00:15:20,550 --> 00:15:23,100
Now node dot left and node dot right.

363
00:15:23,100 --> 00:15:27,660
For this particular node is done which is the node that we made over here with the value four.

364
00:15:27,660 --> 00:15:29,100
Right with the value four.

365
00:15:29,100 --> 00:15:30,390
And then it's going to return.

366
00:15:30,390 --> 00:15:35,610
That means this operation over here which we made a placeholder for is going to be executed.

367
00:15:35,610 --> 00:15:37,860
And this four is going to be placed over here.

368
00:15:37,860 --> 00:15:38,910
So we have four over here.

369
00:15:38,910 --> 00:15:41,070
And towards its left we have null.

370
00:15:41,930 --> 00:15:47,180
And for its right we have five, and for the left and right of five we have null.

371
00:15:47,210 --> 00:15:49,220
So this is how the function works.

372
00:15:49,220 --> 00:15:52,820
So let's just write this in a clean manner over here once more.

373
00:15:52,850 --> 00:15:56,150
So let's take a look at how the binary search tree looks like.

374
00:15:56,150 --> 00:15:56,630
Right.

375
00:15:56,750 --> 00:16:00,710
So uh, so we have three over here at the root.

376
00:16:01,880 --> 00:16:02,210
It is.

377
00:16:02,210 --> 00:16:03,140
Clear this up.

378
00:16:04,230 --> 00:16:05,940
And write it in a neat manner.

379
00:16:05,940 --> 00:16:11,640
So we have three over here and then towards its left we have one towards its right we have four.

380
00:16:11,640 --> 00:16:16,500
And then for one it only has something towards this right which is two.

381
00:16:16,500 --> 00:16:20,070
And for four we only have something towards its right which is five.

382
00:16:20,070 --> 00:16:22,890
So this is how our binary search tree looks like.

383
00:16:22,890 --> 00:16:26,130
And we can see that it is following the binary search tree property.

384
00:16:26,130 --> 00:16:27,570
And it is height balanced.

385
00:16:27,570 --> 00:16:28,950
So yes it's working.

386
00:16:28,950 --> 00:16:30,000
So our code is working.

387
00:16:30,000 --> 00:16:32,820
Now what about the space and time complexity of this solution?

388
00:16:32,820 --> 00:16:37,860
The time complexity of this solution is going to be O of N, because we have to go through each element

389
00:16:37,860 --> 00:16:42,090
in the array which is given to us and make it a node and do some constant time operations.

390
00:16:42,090 --> 00:16:42,360
Right.

391
00:16:42,360 --> 00:16:44,850
So we have to traverse through the array.

392
00:16:44,850 --> 00:16:49,620
So that's why for each instance and after while we traverse the array for each instance, we have to

393
00:16:49,620 --> 00:16:52,440
do some constant time operations like making a node.

394
00:16:52,440 --> 00:16:54,990
And then we go ahead and return the node.

395
00:16:54,990 --> 00:16:55,260
Right.

396
00:16:55,260 --> 00:16:59,160
So we have already accounted for these as traversing the array.

397
00:16:59,160 --> 00:17:01,950
So that's why the time complexity is going to be O of n.

398
00:17:01,950 --> 00:17:04,200
And what about the space complexity.

399
00:17:04,200 --> 00:17:10,170
The space complexity of this solution is going to be of the order of the height or the maximum depth

400
00:17:10,170 --> 00:17:11,550
of the binary search tree.

401
00:17:11,550 --> 00:17:12,090
All right.

402
00:17:13,080 --> 00:17:18,300
However, you can also say that there is space consumed because we are returning the binary search tree,

403
00:17:18,300 --> 00:17:18,570
right?

404
00:17:18,570 --> 00:17:20,010
We are building the binary search tree.

405
00:17:20,010 --> 00:17:25,590
So for that, the space complexity is going to be O of n, because in the binary search tree there is

406
00:17:25,590 --> 00:17:26,790
going to be n elements.

407
00:17:26,790 --> 00:17:30,360
So the call stack is going to take O of log n space.

408
00:17:30,360 --> 00:17:32,010
But then n is greater than log n.

409
00:17:32,010 --> 00:17:36,090
So we can say that the space complexity of this solution is o of n.