1
00:00:00,720 --> 00:00:01,800
Welcome back.

2
00:00:01,800 --> 00:00:06,810
In this video, let's take a look at how we can write our insert function.

3
00:00:06,810 --> 00:00:10,320
And as it is mentioned in the question we will be given an array.

4
00:00:10,320 --> 00:00:12,780
Let's say this is the array which is given to us.

5
00:00:12,780 --> 00:00:17,850
So we will have a variable, let's call it I, which will be used to traverse the array which is given

6
00:00:17,850 --> 00:00:18,330
to us.

7
00:00:18,330 --> 00:00:21,300
Now at this point our binary tree is empty.

8
00:00:21,300 --> 00:00:22,290
Let's say it's empty.

9
00:00:22,290 --> 00:00:22,770
All right.

10
00:00:22,770 --> 00:00:24,750
And we also will need a queue.

11
00:00:24,750 --> 00:00:25,830
And we start over here.

12
00:00:25,830 --> 00:00:28,350
So we have to make this our root node right.

13
00:00:28,350 --> 00:00:31,620
So we take the root and we will insert it to our queue.

14
00:00:32,210 --> 00:00:35,060
Now because the binary tree at this point is empty.

15
00:00:35,090 --> 00:00:40,100
We will take this node, the the value over here, we will make it to a node and we will make it the

16
00:00:40,100 --> 00:00:42,110
root of our binary tree.

17
00:00:42,110 --> 00:00:44,900
So we have seven over here which is our root node.

18
00:00:44,900 --> 00:00:47,870
And in our queue we have our root node over here.

19
00:00:47,870 --> 00:00:48,440
All right.

20
00:00:48,470 --> 00:00:50,300
Now we have used up this element.

21
00:00:50,300 --> 00:00:53,300
Now therefore we will just shift I to the next element.

22
00:00:53,330 --> 00:01:00,500
Now if it was given if we were calling this insert function where the binary tree already has a node

23
00:01:00,500 --> 00:01:01,160
at the root.

24
00:01:01,160 --> 00:01:05,030
In that case we will just continue with I over here and the method will be the same.

25
00:01:05,030 --> 00:01:05,390
All right.

26
00:01:05,390 --> 00:01:09,110
So in that case we will just insert the root node to our queue.

27
00:01:09,110 --> 00:01:10,190
And then we will proceed.

28
00:01:10,190 --> 00:01:11,840
And I would not be shifted ahead.

29
00:01:11,840 --> 00:01:15,200
But over here let's say the binary tree was initially empty.

30
00:01:15,200 --> 00:01:18,800
So we have used up this value over here to create a node.

31
00:01:18,800 --> 00:01:20,420
And that has been made the root node.

32
00:01:20,420 --> 00:01:22,700
And the root node is added to our queue.

33
00:01:22,700 --> 00:01:24,140
So this is where we are at.

34
00:01:24,140 --> 00:01:26,510
And we have shifted I to the next element.

35
00:01:26,510 --> 00:01:31,730
So I is pointing to 11 over here which is at index two which is at index one.

36
00:01:32,210 --> 00:01:32,690
All right.

37
00:01:32,690 --> 00:01:36,980
Now what we will do is we will do something very much similar to breadth first search.

38
00:01:36,980 --> 00:01:38,690
So we will have a while loop.

39
00:01:38,690 --> 00:01:42,920
And as long as something is there in the queue we will keep looping.

40
00:01:42,920 --> 00:01:45,950
So if something is there in the queue we will dequeue.

41
00:01:46,040 --> 00:01:48,350
That would be the first step similar to breadth first search.

42
00:01:48,350 --> 00:01:50,600
So we take out this seven over here.

43
00:01:50,660 --> 00:01:51,200
All right.

44
00:01:51,200 --> 00:01:54,710
And now we are going to check if there is something to its left.

45
00:01:54,980 --> 00:01:55,430
All right.

46
00:01:55,430 --> 00:02:00,050
So if there is nothing on its left what we will do is we will take this value.

47
00:02:00,050 --> 00:02:01,430
If it is not null right.

48
00:02:01,430 --> 00:02:03,170
If it is null, we won't take it.

49
00:02:03,170 --> 00:02:05,330
But over here we can see this is not null.

50
00:02:05,330 --> 00:02:10,520
So if it is not null, if the value is not null, we will take it and we will make it to a node.

51
00:02:10,520 --> 00:02:12,170
We will make this a node.

52
00:02:12,170 --> 00:02:14,390
And then we will add it to the left over here.

53
00:02:14,390 --> 00:02:14,750
All right.

54
00:02:14,750 --> 00:02:17,480
So at the present moment nothing is there over here.

55
00:02:17,480 --> 00:02:20,000
So we will we will add it to the left of the current node.

56
00:02:20,000 --> 00:02:21,770
And then we will increment I.

57
00:02:21,800 --> 00:02:23,030
We will increment I.

58
00:02:23,060 --> 00:02:28,370
So I will point to the index two which is the next value over here which is one over here.

59
00:02:28,370 --> 00:02:28,790
All right.

60
00:02:28,820 --> 00:02:32,120
Now we have something over here in the left right.

61
00:02:32,120 --> 00:02:37,880
So we need to enqueue it to our queue so that in the next pass right when we go to the next level,

62
00:02:37,880 --> 00:02:41,090
we will check whether there is something to its left or to its right.

63
00:02:41,090 --> 00:02:43,460
So that's why we need to keep enqueuing elements.

64
00:02:43,460 --> 00:02:48,170
So at this point we are just going to enqueue what is there on the left of our current node.

65
00:02:48,170 --> 00:02:51,230
So we put this 11 over here to our queue.

66
00:02:51,230 --> 00:02:51,500
All right.

67
00:02:51,500 --> 00:02:52,880
So we are going to enqueue this.

68
00:02:52,880 --> 00:02:55,280
Now let's just write it into our queue.

69
00:02:55,790 --> 00:03:02,150
Now if it was the case that the tree which is given to us already had a few nodes, for example, it

70
00:03:02,390 --> 00:03:03,680
already had something over here.

71
00:03:03,680 --> 00:03:07,070
In that case we would see that there is something on the left.

72
00:03:07,070 --> 00:03:08,480
So this would not execute.

73
00:03:08,480 --> 00:03:10,640
But this will still execute, right?

74
00:03:10,820 --> 00:03:15,710
Because it's there, we will still put it to our queue because we want to in the next pass.

75
00:03:15,710 --> 00:03:20,540
When we dequeue this we will check for the children positions of this particular node.

76
00:03:20,540 --> 00:03:21,110
All right.

77
00:03:21,110 --> 00:03:22,580
So we have done this for the left.

78
00:03:22,580 --> 00:03:25,910
And I has shifted to index two over here.

79
00:03:25,910 --> 00:03:26,180
Right.

80
00:03:26,180 --> 00:03:27,260
This is index two.

81
00:03:27,350 --> 00:03:28,790
This is zero one and two.

82
00:03:28,820 --> 00:03:30,740
So I is at index two at this point.

83
00:03:30,740 --> 00:03:36,170
Now whatever we did for left right these two steps we are going to repeat the same thing for the right

84
00:03:36,170 --> 00:03:38,000
as well the right of this current node.

85
00:03:38,000 --> 00:03:40,760
So we are going to check if there is something in the right.

86
00:03:40,760 --> 00:03:44,450
And then we we will enqueue that particular node to our queue.

87
00:03:44,450 --> 00:03:46,070
So so that is what we're going to do.

88
00:03:46,070 --> 00:03:48,590
So at this point nothing is there on the right.

89
00:03:48,590 --> 00:03:52,280
So what we will do is we will take the value and check whether it's null.

90
00:03:52,280 --> 00:03:53,630
So we see it's not null.

91
00:03:53,630 --> 00:03:55,760
So we will create a node out of it.

92
00:03:55,760 --> 00:03:59,870
And then we will insert it at the right of the current node which is over here.

93
00:03:59,870 --> 00:04:00,170
All right.

94
00:04:00,170 --> 00:04:01,040
So let's do that.

95
00:04:01,040 --> 00:04:03,050
And then we will just increment I.

96
00:04:03,080 --> 00:04:04,850
So over here we will increment I.

97
00:04:04,880 --> 00:04:08,180
So we get I to the next value in our array.

98
00:04:08,180 --> 00:04:10,700
And then we will check if there is something in the right.

99
00:04:10,700 --> 00:04:13,040
So because we just now inserted it will be there.

100
00:04:13,040 --> 00:04:18,560
Now even if the tree was existing already and there was something at the right, we would have put it,

101
00:04:18,650 --> 00:04:19,790
pushed it to our queue.

102
00:04:19,790 --> 00:04:23,330
So at this point we pushed this to our enqueue to our queue.

103
00:04:23,330 --> 00:04:23,870
All right.

104
00:04:24,440 --> 00:04:25,850
So let's get one over here.

105
00:04:25,850 --> 00:04:28,580
Now you can see this is similar to breadth first search right.

106
00:04:28,580 --> 00:04:34,280
These steps this and this and Dequeuing this is there in our typical vanilla breadth first search which

107
00:04:34,280 --> 00:04:35,090
we have discussed.

108
00:04:35,090 --> 00:04:35,390
All right.

109
00:04:35,390 --> 00:04:37,340
So let's just clear this space.

110
00:04:37,340 --> 00:04:39,350
So we've got 11 and one over here.

111
00:04:39,350 --> 00:04:42,440
And we our eye is now pointing to null.

112
00:04:42,440 --> 00:04:42,740
All right.

113
00:04:42,740 --> 00:04:43,820
So this part is over.

114
00:04:43,820 --> 00:04:48,320
Now again we come over here and we see that we have these two elements in our queue.

115
00:04:48,320 --> 00:04:50,030
So the queue is not empty.

116
00:04:50,030 --> 00:04:52,610
So we come inside the while loop and we dequeue.

117
00:04:52,610 --> 00:04:53,870
So we dequeue 11.

118
00:04:53,930 --> 00:04:56,900
Now we are going to check its left and right.

119
00:04:56,900 --> 00:04:59,330
So over here the value is null.

120
00:04:59,330 --> 00:05:03,950
So when we come to its left though the left is empty right.

121
00:05:03,950 --> 00:05:04,370
We don't.

122
00:05:04,370 --> 00:05:04,850
It's null.

123
00:05:04,850 --> 00:05:07,400
So the left of 11 is at this point level null.

124
00:05:07,400 --> 00:05:08,720
So we don't have anything over here.

125
00:05:08,720 --> 00:05:11,420
So we could have inserted at the left of this node.

126
00:05:11,420 --> 00:05:13,220
But then the value over here is null.

127
00:05:13,220 --> 00:05:15,500
So we just go ahead and increment I.

128
00:05:15,530 --> 00:05:17,600
So we increment I and we move on.

129
00:05:17,600 --> 00:05:20,210
Now we come over here and we check its right.

130
00:05:20,210 --> 00:05:22,310
We see that its right is also null.

131
00:05:22,310 --> 00:05:24,890
So we can create a node out of this value.

132
00:05:24,890 --> 00:05:27,380
And we will insert it at the right of 11.

133
00:05:27,830 --> 00:05:29,270
And then we will increment I.

134
00:05:29,300 --> 00:05:31,250
So we increment I and we move over.

135
00:05:31,760 --> 00:05:34,670
And then we are going to enqueue this element to our queue.

136
00:05:34,670 --> 00:05:36,350
So we get seven to our queue.

137
00:05:36,380 --> 00:05:40,700
Again we come over here, we see that we have these two elements in our queue right.

138
00:05:40,910 --> 00:05:42,110
These two are there in our queue.

139
00:05:42,110 --> 00:05:47,180
So we'd queue again and we have dequeue this node over here at this point.

140
00:05:47,180 --> 00:05:48,980
And now we are going to check its left.

141
00:05:48,980 --> 00:05:51,260
And right now there is nothing in its left.

142
00:05:51,260 --> 00:05:54,980
And so we can make a node out of this value which is two.

143
00:05:54,980 --> 00:05:56,630
And we insert it at its left.

144
00:05:56,630 --> 00:05:58,820
And over here we are just going to increment I.

145
00:05:58,850 --> 00:05:59,990
So we come over here.

146
00:05:59,990 --> 00:06:01,250
Now we check its right.

147
00:06:01,250 --> 00:06:02,540
So there is nothing in its right.

148
00:06:02,540 --> 00:06:06,590
So we make a node out of this value and we put it over here.

149
00:06:06,590 --> 00:06:08,780
And again before that we have to enqueue this two.

150
00:06:08,810 --> 00:06:10,520
So we enqueue two over here.

151
00:06:10,520 --> 00:06:14,030
Then we come over here we we make a node out of this value.

152
00:06:14,030 --> 00:06:18,110
And we say that the right of the current node is this node over here.

153
00:06:18,110 --> 00:06:20,150
And then we are going to enqueue this also.

154
00:06:20,150 --> 00:06:20,300
Right.

155
00:06:20,300 --> 00:06:22,640
So we get a eight also over here.

156
00:06:22,640 --> 00:06:23,900
And then we push I ahead.

157
00:06:23,900 --> 00:06:27,560
So I comes over here and we get eight also to our queue.

158
00:06:27,560 --> 00:06:29,090
Again we come to the while loop.

159
00:06:29,090 --> 00:06:30,230
We check this condition.

160
00:06:30,230 --> 00:06:33,410
We see that the queue is not empty at this point.

161
00:06:33,410 --> 00:06:38,660
So we dequeue, we take out seven and we are going to check its left and right.

162
00:06:38,660 --> 00:06:41,480
We see that its left and right are empty, right.

163
00:06:41,480 --> 00:06:44,900
So again we come over here, we see its left is empty.

164
00:06:44,900 --> 00:06:46,610
So we have the value.

165
00:06:46,610 --> 00:06:48,920
But the value over here is pointing to null right.

166
00:06:48,920 --> 00:06:54,710
So we ignore and we proceed ahead and we increase the value of I.

167
00:06:54,740 --> 00:06:55,010
Right.

168
00:06:55,010 --> 00:06:56,390
So we come to the next element.

169
00:06:56,390 --> 00:06:57,620
This also is null.

170
00:06:57,620 --> 00:07:01,910
So when we check its right even though its right also is is null.

171
00:07:01,910 --> 00:07:03,410
We could have inserted the value.

172
00:07:03,410 --> 00:07:07,370
But because this is null we don't create a node and we proceed ahead right.

173
00:07:07,370 --> 00:07:08,570
And we increment I.

174
00:07:08,600 --> 00:07:11,420
So we increment I and we come over here again.

175
00:07:11,420 --> 00:07:14,210
We come over here, we see that the queue is not empty.

176
00:07:14,210 --> 00:07:16,640
So we take this element over here which is two.

177
00:07:16,640 --> 00:07:18,620
And we are going to check its left and right.

178
00:07:18,650 --> 00:07:20,420
Now its left is also empty.

179
00:07:20,420 --> 00:07:23,690
But because this is pointing to a null we proceed ahead, right?

180
00:07:23,690 --> 00:07:26,420
So we increment I and we proceed ahead.

181
00:07:26,420 --> 00:07:32,120
And at this point we check its right and we see that its right is also pointing to null.

182
00:07:32,120 --> 00:07:35,420
So we make a value a node out of this value.

183
00:07:35,420 --> 00:07:38,630
And we insert it over here which is the right of this node.

184
00:07:38,630 --> 00:07:39,140
All right.

185
00:07:39,140 --> 00:07:44,750
And then we are going to enqueue this right at this step we're going to enqueue it out into our queue.

186
00:07:44,750 --> 00:07:46,160
So we get three over here.

187
00:07:47,700 --> 00:07:48,120
All right.

188
00:07:48,120 --> 00:07:50,700
So we get three over here and we increment I.

189
00:07:50,730 --> 00:07:52,590
So we have three in our queue.

190
00:07:52,590 --> 00:07:54,480
And we incremented I to null.

191
00:07:54,480 --> 00:07:56,520
Now we are again back.

192
00:07:56,520 --> 00:07:57,630
We are checking our queue.

193
00:07:57,630 --> 00:07:58,860
Our queue is not empty.

194
00:07:58,860 --> 00:08:04,020
So we dequeue we dequeue this eight over here and we are checking its left and right over here.

195
00:08:04,020 --> 00:08:05,880
And these two are empty.

196
00:08:05,880 --> 00:08:08,670
But because it's null over here we're just going to proceed.

197
00:08:08,670 --> 00:08:08,850
Right.

198
00:08:08,850 --> 00:08:12,450
We will just increment I and we will just increment I again.

199
00:08:12,450 --> 00:08:15,600
So this part is done and we come over here again.

200
00:08:15,600 --> 00:08:17,490
We check our while loop.

201
00:08:17,490 --> 00:08:18,660
The queue is not empty.

202
00:08:18,690 --> 00:08:20,130
We have three at this point.

203
00:08:20,130 --> 00:08:23,460
So we dequeue three and we are going to check its left and right.

204
00:08:23,490 --> 00:08:25,320
Now its left and right are empty.

205
00:08:25,320 --> 00:08:26,820
So over here we have five.

206
00:08:26,820 --> 00:08:32,010
We will make a node out of this and we insert it at the left of this particular node.

207
00:08:32,010 --> 00:08:37,140
And then we will increment I and we will push I to this five to our queue.

208
00:08:37,140 --> 00:08:39,270
Again we come to the right of this.

209
00:08:39,270 --> 00:08:41,640
And because the value over here is null.

210
00:08:41,640 --> 00:08:44,790
So at this point we we are done with our array.

211
00:08:44,790 --> 00:08:44,970
Right.

212
00:08:44,970 --> 00:08:49,620
So we have completed our array and we don't insert anything over here because this value over here is

213
00:08:49,620 --> 00:08:49,980
null.

214
00:08:49,980 --> 00:08:54,540
Now we will when we increment I, we will see that I will be equal to the length of the array.

215
00:08:54,540 --> 00:08:57,600
So we have nothing more to check for inserting.

216
00:08:57,600 --> 00:08:59,910
So at this point we can come out of this loop.

217
00:08:59,910 --> 00:09:02,760
So this is how we will go ahead and write this function.

218
00:09:02,760 --> 00:09:06,720
Now in the next video let's try to code this out together.