1
00:00:00,650 --> 00:00:01,700
Welcome back.

2
00:00:01,700 --> 00:00:06,080
Let's now go ahead and write the insert function which we just now discussed.

3
00:00:06,080 --> 00:00:08,360
So over here we have our node class.

4
00:00:08,360 --> 00:00:10,790
So we will use this to create each node.

5
00:00:10,790 --> 00:00:13,730
And then we have our binary tree class over here.

6
00:00:13,730 --> 00:00:16,520
And over here is our insert function.

7
00:00:16,520 --> 00:00:19,760
Now an array will be passed to it which has values in it.

8
00:00:19,760 --> 00:00:22,670
We will take each value and we will make a node out of it.

9
00:00:22,670 --> 00:00:24,800
And we will insert it to the binary tree.

10
00:00:24,800 --> 00:00:26,870
So this is what we are trying to do over here.

11
00:00:26,870 --> 00:00:28,730
Now let's get started with this function.

12
00:00:28,730 --> 00:00:32,690
And again over here you can see I have created three is equal to new binary tree.

13
00:00:32,690 --> 00:00:34,460
And then we have called the insert function.

14
00:00:34,460 --> 00:00:36,380
And we have passed this array over here.

15
00:00:36,380 --> 00:00:38,870
And again we wanted to insert more values.

16
00:00:38,870 --> 00:00:41,600
So over here we have again called the same function.

17
00:00:41,600 --> 00:00:43,640
And we have passed this array over here.

18
00:00:43,640 --> 00:00:44,090
All right.

19
00:00:44,090 --> 00:00:46,580
So let's go ahead and complete this function over here.

20
00:00:46,580 --> 00:00:50,480
First we are going to check if the array does not have any value in it.

21
00:00:50,480 --> 00:00:52,640
So if array dot length.

22
00:00:54,680 --> 00:00:57,590
If that is equal to zero, then we can just return.

23
00:00:58,320 --> 00:00:58,800
All right.

24
00:00:58,800 --> 00:01:02,700
Now, if this is not the case, we're going to check if the root is null.

25
00:01:03,820 --> 00:01:08,500
For example, over here you can see we have called the function for the first time right.

26
00:01:08,500 --> 00:01:09,190
The insert value.

27
00:01:09,190 --> 00:01:12,850
And there is no value or no node in the binary tree at this point.

28
00:01:12,850 --> 00:01:18,580
So when we call this this function over here, we'll have to take the first value and make it a node.

29
00:01:18,580 --> 00:01:21,310
And we have to make that particular node the root node.

30
00:01:21,310 --> 00:01:23,050
So that is what we are checking over here.

31
00:01:23,050 --> 00:01:25,990
Now let me have a variable I.

32
00:01:26,020 --> 00:01:28,060
So let's say let I is equal to zero.

33
00:01:28,060 --> 00:01:31,510
Now we will use I to traverse the array which is given to us.

34
00:01:31,510 --> 00:01:32,110
All right.

35
00:01:32,140 --> 00:01:34,990
Now let's go ahead and check if the root is null.

36
00:01:34,990 --> 00:01:38,950
So for this we are just going to say if not this dot root.

37
00:01:39,850 --> 00:01:40,120
Right.

38
00:01:40,120 --> 00:01:41,800
So that means the root is null.

39
00:01:41,800 --> 00:01:43,750
So no node is there over here.

40
00:01:43,750 --> 00:01:47,530
So we are going to take the first value from the array and make it the root.

41
00:01:47,530 --> 00:01:53,020
So before we do that we also have to check whether this value over here which is passed is null or not.

42
00:01:53,020 --> 00:01:53,200
Right.

43
00:01:53,200 --> 00:01:57,550
Because we have seen in the example that sometimes null value also can be passed.

44
00:01:57,550 --> 00:01:59,950
So that is okay if it's not over here.

45
00:01:59,950 --> 00:02:04,900
But if the first value itself is null and the tree does not have a root, then we will just return.

46
00:02:04,900 --> 00:02:05,380
All right.

47
00:02:05,380 --> 00:02:06,370
So let's just check that.

48
00:02:06,370 --> 00:02:07,900
So if array at zero.

49
00:02:08,840 --> 00:02:10,430
Is equal to null.

50
00:02:10,430 --> 00:02:13,730
If this is the case, then also we will just return.

51
00:02:14,480 --> 00:02:19,100
Now, if this is not the case, then we will go ahead and create a new node.

52
00:02:19,100 --> 00:02:22,610
So let's say let node is equal to new node.

53
00:02:22,610 --> 00:02:25,040
And we will pass the value at the zeroth index.

54
00:02:25,040 --> 00:02:27,110
So array at I or zero.

55
00:02:27,110 --> 00:02:28,580
Again we know that it's zero.

56
00:02:28,580 --> 00:02:30,350
So I'm just writing it over here as zero.

57
00:02:30,350 --> 00:02:32,600
And then we will say this dot root.

58
00:02:33,380 --> 00:02:36,110
Is equal to this node which we just now created.

59
00:02:36,110 --> 00:02:41,420
And after we're done with this, we will increment I, because we have already used up the, uh, the

60
00:02:41,420 --> 00:02:44,690
value at the zeroth index right in the array, which is passed to us.

61
00:02:44,690 --> 00:02:49,970
Now, at this point, we're just going to check if I is equal to the length of the array.

62
00:02:51,500 --> 00:02:53,240
If that is the case, then we are done right?

63
00:02:53,240 --> 00:02:57,050
So if the array which was passed just had one element in it.

64
00:02:57,050 --> 00:02:58,880
Now when initially I is zero.

65
00:02:58,880 --> 00:03:02,210
But when we increment this over here I will become equal to one.

66
00:03:02,210 --> 00:03:04,130
So I would be equal to array dot length.

67
00:03:04,130 --> 00:03:06,050
If the array had only one element right.

68
00:03:06,050 --> 00:03:07,850
The array which which passed to us.

69
00:03:07,850 --> 00:03:09,380
If this had just one over here.

70
00:03:09,380 --> 00:03:11,360
So that that's the case that we're discussing.

71
00:03:11,360 --> 00:03:12,950
In this case we can just return.

72
00:03:12,950 --> 00:03:14,540
So we can say return this.

73
00:03:14,540 --> 00:03:17,960
That means we are returning the, uh, the current, uh, binary tree.

74
00:03:17,960 --> 00:03:18,230
Right.

75
00:03:18,230 --> 00:03:19,340
So when we call it.

76
00:03:19,340 --> 00:03:20,060
All right.

77
00:03:20,480 --> 00:03:21,560
So that's it.

78
00:03:21,560 --> 00:03:27,500
So we have we are done with creating this part where we took the first element and we make it the root.

79
00:03:27,500 --> 00:03:29,660
If the root is not there.

80
00:03:29,660 --> 00:03:31,670
And then we are just going to continue.

81
00:03:31,670 --> 00:03:33,920
Now we are out of this function.

82
00:03:33,920 --> 00:03:35,240
Now let's just continue.

83
00:03:35,240 --> 00:03:39,830
And again, as we've seen, we are just going to insert the remaining elements and we will be using

84
00:03:39,830 --> 00:03:40,790
a queue for this.

85
00:03:41,450 --> 00:03:42,080
All right.

86
00:03:42,590 --> 00:03:45,560
Now initially the queue will just have the root.

87
00:03:45,560 --> 00:03:47,840
So let's just say const queue.

88
00:03:49,200 --> 00:03:50,190
Is equal to.

89
00:03:50,190 --> 00:03:55,650
And again we are using an array because this is JavaScript and there is no inbuilt queue data structure

90
00:03:55,650 --> 00:03:56,520
in JavaScript.

91
00:03:56,520 --> 00:04:03,780
And for this to work in optimal time complexity, we would have to use a linked list to create the queue.

92
00:04:03,780 --> 00:04:08,550
But then to save time and because that is not the central part in this question, we're just going to

93
00:04:08,550 --> 00:04:09,720
use an array over here.

94
00:04:10,200 --> 00:04:14,460
Now you can mention this to your interviewer if he or she is asking you to write this.

95
00:04:14,460 --> 00:04:18,930
So you can say that you're using an array over here just to save time.

96
00:04:18,930 --> 00:04:20,790
And most probably they'll be okay with it.

97
00:04:20,790 --> 00:04:26,280
So over here we say const queue and then we have the root already inserted to the queue.

98
00:04:26,280 --> 00:04:28,170
So we say this dot root over here.

99
00:04:28,170 --> 00:04:30,000
Now we are going to have a while loop.

100
00:04:30,000 --> 00:04:33,900
And as long as something is there in the queue we will just keep looping.

101
00:04:33,900 --> 00:04:35,490
So while queue dot length.

102
00:04:37,090 --> 00:04:37,570
All right.

103
00:04:37,570 --> 00:04:41,920
So this is um again similar to breadth first search, what we've discussed.

104
00:04:41,920 --> 00:04:44,140
So this is the same thing that we are using over here.

105
00:04:44,140 --> 00:04:46,450
Now let's take the first element from the queue.

106
00:04:46,450 --> 00:04:49,300
So let current is equal to.

107
00:04:50,550 --> 00:04:51,630
Q dot shift.

108
00:04:52,470 --> 00:04:54,780
So we're taking the first element from the queue.

109
00:04:54,780 --> 00:04:57,390
So again the queue Q is a Fifo data structure.

110
00:04:57,390 --> 00:04:58,290
First in first out.

111
00:04:58,290 --> 00:05:03,960
Right now we're going to check for the left side of the current node whether it's empty or not.

112
00:05:03,960 --> 00:05:08,040
So let's just check that if current dot if not current dot left right.

113
00:05:08,040 --> 00:05:10,950
That means there is nothing to the left of the current node.

114
00:05:10,950 --> 00:05:15,600
If that is the case, and if the value at the ith index is not null.

115
00:05:15,600 --> 00:05:16,590
So let's just check that.

116
00:05:16,590 --> 00:05:18,840
If not if array at I.

117
00:05:18,870 --> 00:05:20,160
Let's say if array at I.

118
00:05:21,210 --> 00:05:22,770
Not equal to null.

119
00:05:23,980 --> 00:05:28,750
So if this is not equal to null, then we will just create a node with that value.

120
00:05:29,050 --> 00:05:31,390
And then we will insert it at current dot left.

121
00:05:31,390 --> 00:05:35,830
So let's say let node is equal to new node.

122
00:05:35,830 --> 00:05:37,510
And then we pass the value.

123
00:05:37,510 --> 00:05:39,280
So array at I right.

124
00:05:39,280 --> 00:05:40,810
So we create a node.

125
00:05:40,810 --> 00:05:43,330
And then we are going to say current dot left.

126
00:05:45,020 --> 00:05:46,550
Is equal to node.

127
00:05:47,180 --> 00:05:51,620
And once we're done with this we have used up the element at the ith index.

128
00:05:51,620 --> 00:05:52,730
So we have to increment I.

129
00:05:52,760 --> 00:05:54,110
So we say I plus plus.

130
00:05:54,110 --> 00:05:58,040
And then again we're just going to check if I is equal to array dot length.

131
00:05:58,190 --> 00:06:02,660
If that is the case then we just inserted the last element in the given array.

132
00:06:02,660 --> 00:06:05,810
So we can just uh return the binary tree.

133
00:06:05,810 --> 00:06:05,990
Right.

134
00:06:05,990 --> 00:06:08,540
So return this and we come out of this.

135
00:06:08,930 --> 00:06:09,500
All right.

136
00:06:09,500 --> 00:06:16,160
So once we are done with this we also have to enqueue the element right at the left.

137
00:06:16,160 --> 00:06:18,770
So let's again say if current dot left.

138
00:06:20,260 --> 00:06:21,730
And we're just going to NQ.

139
00:06:21,730 --> 00:06:24,730
So over here we'll just say Q dot push.

140
00:06:25,330 --> 00:06:27,940
And we will push current dot left to the q.

141
00:06:29,760 --> 00:06:30,150
Right.

142
00:06:30,150 --> 00:06:32,640
So this is the same thing that we discussed in the video.

143
00:06:32,640 --> 00:06:37,890
So we are doing we are pushing it to the queue because again later at the later point we want to see

144
00:06:37,890 --> 00:06:40,170
if we have to insert more elements.

145
00:06:40,170 --> 00:06:44,730
We have to see the left and right of this particular node, which we now just now enqueued.

146
00:06:44,730 --> 00:06:48,630
So that is why we are putting it back to our queue and we are done with this part.

147
00:06:49,430 --> 00:06:52,190
Now let's proceed and do the same thing for the right.

148
00:06:52,190 --> 00:06:53,540
So this was for the left.

149
00:06:53,540 --> 00:06:53,990
All right.

150
00:06:53,990 --> 00:06:59,030
So that this started over here and we pushed it to the queue.

151
00:06:59,030 --> 00:06:59,720
So we are done.

152
00:06:59,720 --> 00:07:01,460
Now we are doing the same thing for the right.

153
00:07:01,460 --> 00:07:01,760
All right.

154
00:07:01,760 --> 00:07:03,800
So let me just write a comment over here.

155
00:07:03,800 --> 00:07:05,060
And then it's the same thing.

156
00:07:05,060 --> 00:07:07,490
We are just checking whether the current is there.

157
00:07:07,490 --> 00:07:10,400
So if if there is there something at current dot.

158
00:07:10,400 --> 00:07:10,760
Right.

159
00:07:10,760 --> 00:07:13,430
So let's say if not current dot right.

160
00:07:14,350 --> 00:07:19,060
So if nothing is there and the value at the ith index should not be null.

161
00:07:19,060 --> 00:07:20,890
So again we are checking if array.

162
00:07:22,550 --> 00:07:26,210
At I if this is not equal to null.

163
00:07:27,030 --> 00:07:29,400
So if this is the case then we will create a node.

164
00:07:29,400 --> 00:07:33,060
So again let node is equal to new node.

165
00:07:33,060 --> 00:07:35,520
And the value that we are passing is array at I.

166
00:07:37,590 --> 00:07:40,020
And we will say current dot right?

167
00:07:41,370 --> 00:07:43,590
Is equal to this particular node.

168
00:07:43,620 --> 00:07:47,730
Now, once we're done with this, we have used up the value at the ith index.

169
00:07:47,730 --> 00:07:49,350
So we have to do I plus plus.

170
00:07:49,350 --> 00:07:53,010
And again we will check whether I is equal to array dot length.

171
00:07:53,010 --> 00:07:58,530
So if that is the case then the value that we just made a node and inserted was the last value in the

172
00:07:58,530 --> 00:07:58,920
array.

173
00:07:58,920 --> 00:08:03,030
So in that case we can just return the binary tree and we can exit the function.

174
00:08:03,030 --> 00:08:05,910
So if I is equal to array dot length.

175
00:08:07,760 --> 00:08:10,820
In this case, we will just return the binary tree.

176
00:08:11,810 --> 00:08:12,260
All right.

177
00:08:12,260 --> 00:08:17,270
Now, once we are done with this, we also have to enqueue the current element.

178
00:08:17,270 --> 00:08:18,050
So again.

179
00:08:19,240 --> 00:08:22,240
We say if current dot right.

180
00:08:23,420 --> 00:08:24,560
Then we will NQ it.

181
00:08:24,560 --> 00:08:26,270
So we say q dot push.

182
00:08:29,420 --> 00:08:32,150
And we pass in current dot, right?

183
00:08:33,370 --> 00:08:33,790
All right.

184
00:08:33,790 --> 00:08:34,720
So that is it.

185
00:08:34,720 --> 00:08:37,660
So that brings us to the end of the function.

186
00:08:37,660 --> 00:08:40,360
So once we are out of this while loop we are done.

187
00:08:40,360 --> 00:08:43,210
So we'll have inserted all the values.

188
00:08:44,830 --> 00:08:48,520
Now let's go ahead and run the function and test our code.

189
00:08:48,550 --> 00:08:50,530
So over here we have some values.

190
00:08:50,530 --> 00:08:52,720
Let's try running this code.

191
00:08:52,750 --> 00:08:53,350
All right.

192
00:08:53,350 --> 00:08:56,830
And let's take a look at the binary tree that we get.

193
00:08:59,240 --> 00:09:01,130
So we have the node.

194
00:09:01,130 --> 00:09:02,600
So let's just take a look over here.

195
00:09:02,600 --> 00:09:06,800
We have inserted the values 12345 and then 678.

196
00:09:06,800 --> 00:09:09,800
So we have the node with value one which is correct.

197
00:09:09,800 --> 00:09:12,980
And then on its left and right we should get two and three right.

198
00:09:12,980 --> 00:09:15,710
So let's just draw this out for for us to visualize it.

199
00:09:15,710 --> 00:09:17,330
Let me just draw this out over here.

200
00:09:17,330 --> 00:09:20,480
And then we will just try to compare it with the output that we got.

201
00:09:21,140 --> 00:09:21,680
All right.

202
00:09:21,680 --> 00:09:26,960
So this is the out this is the graph or sorry this is the binary tree that we have just now created.

203
00:09:26,960 --> 00:09:28,310
Now let's take a look.

204
00:09:28,310 --> 00:09:30,440
So we have one over here which is correct.

205
00:09:30,470 --> 00:09:32,450
Now let's open this up.

206
00:09:33,980 --> 00:09:35,600
Now we have two and three.

207
00:09:35,630 --> 00:09:38,240
Two is to the left and three is to the right, which is correct.

208
00:09:38,270 --> 00:09:40,040
Now let's go down this path.

209
00:09:40,040 --> 00:09:42,650
So four and five are over here which is correct.

210
00:09:42,650 --> 00:09:46,160
And then for four we have eight and null which is also correct.

211
00:09:46,370 --> 00:09:47,270
This is correct.

212
00:09:47,270 --> 00:09:50,840
And let me just open it up for five.

213
00:09:50,870 --> 00:09:53,870
So for five it should be just null and null which is also correct.

214
00:09:53,870 --> 00:09:55,460
So we have checked this part.

215
00:09:55,490 --> 00:09:56,660
Now what about this part.

216
00:09:56,660 --> 00:09:58,310
Let's just open up three.

217
00:09:59,060 --> 00:10:01,430
So for three the children are six and seven.

218
00:10:01,430 --> 00:10:02,450
Yes that's correct.

219
00:10:02,450 --> 00:10:04,370
And for six it's null and null.

220
00:10:04,370 --> 00:10:06,830
And for seven also it should be null and null.

221
00:10:06,830 --> 00:10:08,990
So yes our code is working.

222
00:10:08,990 --> 00:10:16,370
Now let's also try to run the same thing for the, um, the array which we discussed in the concept

223
00:10:16,370 --> 00:10:16,880
video.

224
00:10:16,880 --> 00:10:19,460
And let's try to create that same binary tree.

225
00:10:19,460 --> 00:10:21,710
So I have this over here.

226
00:10:22,010 --> 00:10:24,320
Let me just remove this and let's just run it.

227
00:10:24,320 --> 00:10:24,740
All right.

228
00:10:24,740 --> 00:10:26,120
So let me just clear this up.

229
00:10:26,120 --> 00:10:29,930
And we will also try to create the binary tree for this input.

230
00:10:29,930 --> 00:10:31,190
So let's do that together.

231
00:10:32,540 --> 00:10:33,920
So let's do that over here.

232
00:10:33,980 --> 00:10:38,030
Now initially it's seven so we have seven at the root.

233
00:10:40,300 --> 00:10:42,730
And then it's 11 and one over here.

234
00:10:42,730 --> 00:10:44,560
So 11 and one.

235
00:10:44,560 --> 00:10:45,880
And then we have null.

236
00:10:45,880 --> 00:10:49,390
So 11 has a child which is null.

237
00:10:49,390 --> 00:10:50,860
And then we have seven over here.

238
00:10:50,860 --> 00:10:53,830
So we get again seven over here and two and eight.

239
00:10:53,830 --> 00:10:56,380
So we have two and eight over here.

240
00:10:56,800 --> 00:10:58,660
And we have null and null.

241
00:10:58,660 --> 00:11:00,910
So these two are the children of seven.

242
00:11:00,910 --> 00:11:02,350
So these two are null.

243
00:11:03,360 --> 00:11:05,220
And then we have null and three.

244
00:11:05,220 --> 00:11:08,190
So for two there is the left child is null.

245
00:11:08,190 --> 00:11:09,540
The right child is three.

246
00:11:10,360 --> 00:11:12,340
And then we have null and null for this.

247
00:11:12,340 --> 00:11:13,900
This is for eight, right.

248
00:11:13,900 --> 00:11:15,520
This is null and null.

249
00:11:15,520 --> 00:11:17,290
And then we have five and null.

250
00:11:17,290 --> 00:11:19,150
So that is for three right.

251
00:11:19,150 --> 00:11:20,560
Because all of these are already null.

252
00:11:20,560 --> 00:11:23,710
So we don't need to again write null for these cases.

253
00:11:23,710 --> 00:11:25,450
So over here we have five and null.

254
00:11:25,450 --> 00:11:29,350
So it's for this node over here which which will have the children five.

255
00:11:29,350 --> 00:11:30,730
And then this is null.

256
00:11:31,120 --> 00:11:31,420
All right.

257
00:11:31,420 --> 00:11:33,340
So this is how our tree looks like.

258
00:11:33,340 --> 00:11:37,270
Now let me just remove the nulls so that it doesn't get confusing.

259
00:11:38,330 --> 00:11:38,750
Right.

260
00:11:38,750 --> 00:11:40,520
So let's just remove the nulls.

261
00:11:44,080 --> 00:11:46,090
So this is how our tree looks like.

262
00:11:46,090 --> 00:11:49,030
Now just let's run the code and see how it is.

263
00:11:49,030 --> 00:11:53,350
So let's let's see whether we are getting this binary tree using our code.

264
00:11:54,690 --> 00:11:58,440
So let's go ahead and run it and let's take a look at the output.

265
00:11:58,830 --> 00:12:02,040
So we have the node over here which is the root node.

266
00:12:02,040 --> 00:12:02,670
We have seven.

267
00:12:02,670 --> 00:12:03,510
That's correct.

268
00:12:03,510 --> 00:12:05,310
And on its left we have 11.

269
00:12:05,310 --> 00:12:06,690
And on its right we have one.

270
00:12:06,690 --> 00:12:07,470
That's correct.

271
00:12:07,500 --> 00:12:08,910
Now let's check for 11.

272
00:12:08,910 --> 00:12:13,170
The children of 11 the left node is null and the right node is seven which is correct.

273
00:12:13,170 --> 00:12:15,450
And for seven the children are null and null.

274
00:12:15,450 --> 00:12:16,560
So that is also correct.

275
00:12:16,590 --> 00:12:18,060
Now what about for one.

276
00:12:18,060 --> 00:12:19,350
Let's open this up.

277
00:12:19,350 --> 00:12:22,920
For one we can see the left child is two and the right child is eight.

278
00:12:22,920 --> 00:12:23,880
So that's correct.

279
00:12:23,910 --> 00:12:27,750
Now for two the left child is null and the right child is three.

280
00:12:27,750 --> 00:12:28,500
That's correct.

281
00:12:28,500 --> 00:12:31,200
And for three the left child is five.

282
00:12:31,200 --> 00:12:32,640
The right child is null.

283
00:12:32,640 --> 00:12:34,170
And let's just open up five.

284
00:12:34,170 --> 00:12:35,940
Also over here it should be null and null.

285
00:12:35,940 --> 00:12:37,590
So this part also is correct.

286
00:12:37,590 --> 00:12:38,130
All right.

287
00:12:38,130 --> 00:12:40,110
So let's now check for eight.

288
00:12:40,110 --> 00:12:42,030
For eight it should be just null and null.

289
00:12:42,030 --> 00:12:42,540
All right.

290
00:12:42,540 --> 00:12:44,490
So yes our code is working.

291
00:12:44,490 --> 00:12:51,300
Now let's now proceed and see how we can go about the second part of the question.