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

2
00:00:01,580 --> 00:00:06,140
Let's now go ahead and write the function which we discussed in the previous video.

3
00:00:06,140 --> 00:00:09,290
Let's call this function diameter binary tree.

4
00:00:11,230 --> 00:00:15,970
Now this function is going to take in the root of the binary tree.

5
00:00:16,540 --> 00:00:20,500
And let's say initially we say that the max diameter.

6
00:00:21,410 --> 00:00:26,390
Is equal to zero, and we will return the max diameter at the end.

7
00:00:26,390 --> 00:00:28,940
So this is how this function is going to work.

8
00:00:29,120 --> 00:00:29,600
All right.

9
00:00:29,630 --> 00:00:36,320
Now before we start to check for the diameter let's check whether the tree is a null tree.

10
00:00:36,320 --> 00:00:40,730
So if the root is null we will just return zero at that point.

11
00:00:40,730 --> 00:00:44,000
So if not root return zero right.

12
00:00:44,000 --> 00:00:46,730
So if this is not the case we proceed further.

13
00:00:46,730 --> 00:00:51,080
And over here we are going to write a function which we will recursively call.

14
00:00:51,080 --> 00:00:56,150
And let's just say this is DFS because this is going to be depth first search traversal.

15
00:00:56,150 --> 00:00:59,060
And this function is going to take in the node.

16
00:01:00,670 --> 00:01:01,120
All right.

17
00:01:01,120 --> 00:01:05,350
And then finally we are just going to call this function with the root node.

18
00:01:05,350 --> 00:01:06,850
So this is how this is going to work.

19
00:01:06,850 --> 00:01:10,060
So over here we will say DFS root.

20
00:01:12,610 --> 00:01:13,060
All right.

21
00:01:13,090 --> 00:01:18,190
Now let's try to complete this function once we are inside this function, when it is called with a

22
00:01:18,190 --> 00:01:21,100
particular node, we will check if that node is null.

23
00:01:21,100 --> 00:01:24,820
So if not node then we will just return minus one.

24
00:01:24,820 --> 00:01:30,730
Again we have discussed this because the height of a null tree is equal to minus one for conceptual

25
00:01:30,730 --> 00:01:31,360
purposes.

26
00:01:31,360 --> 00:01:34,060
Now the height of a leaf node is equal to zero.

27
00:01:34,060 --> 00:01:37,960
So again that's why the height of a null tree is equal to minus one.

28
00:01:37,960 --> 00:01:41,320
And what we are going to do over here is we are going to find the left height.

29
00:01:41,320 --> 00:01:43,390
So let left height.

30
00:01:45,420 --> 00:01:47,520
Is equal to DFS.

31
00:01:47,670 --> 00:01:49,710
And then we are just going to pass the left node.

32
00:01:49,710 --> 00:01:50,940
So node dot left.

33
00:01:53,170 --> 00:01:53,620
All right.

34
00:01:53,620 --> 00:01:58,960
And the right height is going to be the same where we pass the node at the right side.

35
00:01:58,960 --> 00:02:00,340
So right height.

36
00:02:01,680 --> 00:02:05,310
Is equal to DFS node dot right.

37
00:02:06,470 --> 00:02:09,410
And then over here we will have to return the height.

38
00:02:09,410 --> 00:02:09,590
Right.

39
00:02:09,590 --> 00:02:13,460
So again we are passing the left node and we want to get back the height.

40
00:02:13,490 --> 00:02:17,030
Now over here we should get the height of the left node.

41
00:02:17,030 --> 00:02:19,340
And this should be the height of the right node.

42
00:02:19,340 --> 00:02:23,150
So this is again calling the same DFS function recursively.

43
00:02:23,150 --> 00:02:26,120
So we can say that over here we will have to return the height right.

44
00:02:26,120 --> 00:02:32,210
So the height of a particular node is nothing but the maximum among the height of the left node and

45
00:02:32,210 --> 00:02:33,830
the right node plus one right.

46
00:02:33,830 --> 00:02:38,690
Because the left node and right node are children, so they are one height less than that particular

47
00:02:38,690 --> 00:02:39,020
node.

48
00:02:39,020 --> 00:02:45,980
So we can say return math dot max among left height and right height plus one.

49
00:02:47,060 --> 00:02:50,270
So this over here is the height of that particular node.

50
00:02:50,300 --> 00:02:50,840
All right.

51
00:02:50,840 --> 00:02:55,730
So again we have found the left height and and the right height by recursive calls.

52
00:02:55,760 --> 00:02:58,880
Now the question asks us to find the diameter right.

53
00:02:58,880 --> 00:03:04,970
So we have seen that the diameter is nothing but the sum of the left height and the right height.

54
00:03:04,970 --> 00:03:08,210
And then we have to add one and one because there are two more edges.

55
00:03:08,210 --> 00:03:08,540
Right.

56
00:03:08,540 --> 00:03:11,870
So we can say diameter is equal to left height.

57
00:03:13,000 --> 00:03:14,410
Plus right height.

58
00:03:15,760 --> 00:03:17,680
Plus one plus one.

59
00:03:17,950 --> 00:03:18,250
All right.

60
00:03:18,250 --> 00:03:23,140
So these two we have seen in the previous video we are adding one and one because there is one edge

61
00:03:23,140 --> 00:03:23,890
as we go up.

62
00:03:23,890 --> 00:03:24,160
Right.

63
00:03:24,160 --> 00:03:26,770
So this is the diameter for that particular node.

64
00:03:26,770 --> 00:03:32,830
Now we are going to check whether this diameter is greater than the existing value in max diameter.

65
00:03:32,830 --> 00:03:41,830
So we can say max diameter is equal to math dot max among the current value at max diameter and the

66
00:03:41,830 --> 00:03:44,500
value that we just now calculated which is diameter.

67
00:03:44,500 --> 00:03:49,120
So among these two, whichever is greater that value will be stored to max diameter.

68
00:03:49,120 --> 00:03:51,670
And then we will just return this over here.

69
00:03:51,670 --> 00:03:53,920
So this brings us to the end of this function.

70
00:03:53,920 --> 00:03:58,930
So let's go ahead and call this function and see whether our code is working.

71
00:03:58,930 --> 00:04:01,870
And then we will take a sample input and walk through the code.

72
00:04:01,870 --> 00:04:07,480
So before we start and call this function let me just draw out this binary tree over here which we are

73
00:04:07,480 --> 00:04:10,270
constructing so that we can easily visualize this.

74
00:04:11,030 --> 00:04:11,450
All right.

75
00:04:11,450 --> 00:04:15,170
So I have drawn the binary tree which we have constructed over here.

76
00:04:15,170 --> 00:04:18,110
And now let's go ahead and call this function.

77
00:04:18,110 --> 00:04:20,030
So diameter binary tree.

78
00:04:22,790 --> 00:04:26,690
And we will just pass the root node which is tree dot root.

79
00:04:29,200 --> 00:04:35,020
Now let's go ahead and run our code, and let's take a look at the output so we can see that we are

80
00:04:35,020 --> 00:04:37,990
getting the output as six which is the maximum diameter.

81
00:04:37,990 --> 00:04:39,610
So yes our code is working.

82
00:04:39,610 --> 00:04:40,570
So that would be this.

83
00:04:40,570 --> 00:04:40,780
Right.

84
00:04:40,780 --> 00:04:44,290
So 123456.

85
00:04:44,290 --> 00:04:46,390
So again let me just draw this out over here.

86
00:04:46,390 --> 00:04:50,500
So this diameter six is actually the distance between these two nodes.

87
00:04:50,500 --> 00:04:50,710
Right.

88
00:04:50,710 --> 00:04:56,410
So we have 12345 and six six edges over here.

89
00:04:56,410 --> 00:04:59,590
So that's why the maximum diameter is going to be six.

90
00:04:59,590 --> 00:05:00,580
So this is working.

91
00:05:00,580 --> 00:05:05,170
Now let's take this sample input which is this binary tree over here the root right.

92
00:05:05,170 --> 00:05:06,790
So we are passing this root over here.

93
00:05:06,790 --> 00:05:10,900
And let's walk through the code and take a look at what's happening over here.

94
00:05:10,900 --> 00:05:13,270
So let's just go a little bit up.

95
00:05:13,270 --> 00:05:15,820
So we have our function over here.

96
00:05:16,300 --> 00:05:17,650
And it's now visible.

97
00:05:17,650 --> 00:05:19,060
So this is the binary tree.

98
00:05:19,060 --> 00:05:20,860
And this root is passed to it.

99
00:05:20,860 --> 00:05:23,740
So let's now walk through the code and see what's happening.

100
00:05:23,740 --> 00:05:25,450
So this root is passed to it.

101
00:05:25,450 --> 00:05:26,440
Now we are inside.

102
00:05:26,440 --> 00:05:28,720
Over here we are checking if the root is null.

103
00:05:28,720 --> 00:05:29,770
No it's not null.

104
00:05:29,770 --> 00:05:31,600
So we go ahead over here.

105
00:05:31,600 --> 00:05:33,520
And max diameter is equal to zero.

106
00:05:33,520 --> 00:05:35,290
So let's just trace that over here.

107
00:05:35,290 --> 00:05:38,410
So max diameter at this point is equal to zero.

108
00:05:38,410 --> 00:05:39,880
Then we come over here.

109
00:05:39,880 --> 00:05:42,040
So this is just defining the function.

110
00:05:42,040 --> 00:05:44,830
Then we come over here and we are calling the function with the root.

111
00:05:44,830 --> 00:05:45,310
All right.

112
00:05:45,310 --> 00:05:48,730
So we come over here the root node one is passed.

113
00:05:48,760 --> 00:05:49,990
Now we come inside.

114
00:05:49,990 --> 00:05:52,240
We check if the root if the node is null.

115
00:05:52,240 --> 00:05:52,990
No it's not.

116
00:05:52,990 --> 00:05:55,000
If it was null we would have returned minus one.

117
00:05:55,000 --> 00:06:00,400
Then we come over here and we find the left height is equal to DFS node dot left.

118
00:06:00,400 --> 00:06:02,980
So you can see we are going in this direction right.

119
00:06:02,980 --> 00:06:08,710
So we are calling the same DFS function with this node over here again will come inside.

120
00:06:08,710 --> 00:06:10,480
This will call it on this node.

121
00:06:10,480 --> 00:06:13,000
In this way we will go in this direction.

122
00:06:13,000 --> 00:06:15,670
So we will go depth first and we'll come over here.

123
00:06:15,670 --> 00:06:18,250
Now this will call it on its child which is null.

124
00:06:18,250 --> 00:06:20,140
And that will return back minus one.

125
00:06:20,140 --> 00:06:23,560
Because for the case of null we are returning minus one.

126
00:06:23,560 --> 00:06:25,180
So we are getting minus one over here.

127
00:06:25,180 --> 00:06:27,460
And in this case the right also is null.

128
00:06:27,460 --> 00:06:29,590
So that also will give back minus one.

129
00:06:29,590 --> 00:06:35,860
And we calculate the diameter of this particular node which is minus one plus minus one plus one plus

130
00:06:35,860 --> 00:06:37,060
one which is equal to zero.

131
00:06:37,060 --> 00:06:40,690
So the diameter for this particular node is equal to zero.

132
00:06:40,690 --> 00:06:44,560
And we are checking whether this or the existing value is greater.

133
00:06:44,560 --> 00:06:49,090
So we don't need to swap because we already have zero and we're just getting zero over here.

134
00:06:49,180 --> 00:06:49,810
All right.

135
00:06:49,810 --> 00:06:52,030
And then we are done with this call.

136
00:06:52,030 --> 00:06:52,240
Right.

137
00:06:52,240 --> 00:06:54,400
For this call we are done with the left and the right.

138
00:06:54,400 --> 00:06:58,570
And over here we are going to return the maximum between these two plus one.

139
00:06:58,570 --> 00:06:59,800
So these two are equal.

140
00:06:59,800 --> 00:07:02,920
So we are just going to return minus one plus one right.

141
00:07:02,920 --> 00:07:06,280
So we are going to return from here the height as.

142
00:07:07,020 --> 00:07:09,150
Minus one plus one, which is equal to zero.

143
00:07:09,150 --> 00:07:11,820
So the height zero is going to get returned over here.

144
00:07:11,820 --> 00:07:15,120
So this was part of the left call of this particular node.

145
00:07:15,120 --> 00:07:15,480
Right.

146
00:07:15,480 --> 00:07:16,680
So the left call is done.

147
00:07:16,680 --> 00:07:22,170
When we do the right call for this node we will get back minus one because we have null over here that

148
00:07:22,170 --> 00:07:23,250
will return minus one.

149
00:07:23,250 --> 00:07:23,700
All right.

150
00:07:23,700 --> 00:07:29,160
So diameter in this case will be zero plus minus one which is minus one plus one plus one.

151
00:07:29,160 --> 00:07:30,930
So that that gives us one right.

152
00:07:30,930 --> 00:07:33,750
So we can see that the diameter over here is equal to one.

153
00:07:33,750 --> 00:07:36,480
And that's just the distance between these two nodes.

154
00:07:36,510 --> 00:07:41,880
Because we have one edge over here now because one is greater than what we have existing zero.

155
00:07:41,880 --> 00:07:42,060
Right.

156
00:07:42,060 --> 00:07:43,890
So we have to replace this with one.

157
00:07:43,890 --> 00:07:45,480
And then we come over here.

158
00:07:46,150 --> 00:07:50,140
We are going to return the max between 0 and 1, which is zero plus one.

159
00:07:50,140 --> 00:07:52,480
So from this we are going to return one.

160
00:07:52,480 --> 00:07:53,020
All right.

161
00:07:53,020 --> 00:07:56,110
And again seven on its right it has null.

162
00:07:56,110 --> 00:07:58,330
So that part is going to return minus one.

163
00:07:58,330 --> 00:08:04,270
Now we again calculate the diameter which is one plus minus one which is zero plus one plus one which

164
00:08:04,270 --> 00:08:05,020
is equal to two.

165
00:08:05,020 --> 00:08:05,290
Right.

166
00:08:05,290 --> 00:08:08,920
So the diameter of this node is going to be two which is greater than one.

167
00:08:08,920 --> 00:08:12,430
So we replace that over here which is happening over here right in this line.

168
00:08:12,430 --> 00:08:17,920
And then from here we are going to return the maximum between the left height and the right height.

169
00:08:17,920 --> 00:08:18,850
Over here we have one.

170
00:08:18,850 --> 00:08:20,410
And over here we have minus one.

171
00:08:20,410 --> 00:08:21,910
So one is the greater one.

172
00:08:21,910 --> 00:08:23,050
So one plus one.

173
00:08:23,050 --> 00:08:26,710
So over here we are going to return one plus one which is two right.

174
00:08:26,710 --> 00:08:29,620
So again you can see that this is the height of this.

175
00:08:29,620 --> 00:08:29,890
Right.

176
00:08:29,890 --> 00:08:30,850
So one two.

177
00:08:30,880 --> 00:08:32,260
So that's the height of this node.

178
00:08:32,260 --> 00:08:33,400
And we are returning the height.

179
00:08:33,400 --> 00:08:35,200
So two we are getting two from here.

180
00:08:35,200 --> 00:08:40,330
And in the same manner from this side also because we can see visually it's going to be the same right

181
00:08:40,330 --> 00:08:40,870
over here.

182
00:08:40,870 --> 00:08:41,830
It's the height.

183
00:08:41,860 --> 00:08:42,940
The height is zero.

184
00:08:42,970 --> 00:08:44,620
The height is one the height is two.

185
00:08:44,620 --> 00:08:46,780
So over here also we are going to return two.

186
00:08:46,780 --> 00:08:47,050
Again.

187
00:08:47,050 --> 00:08:51,130
It will go all the way down and then it will come back because this is a recursive call.

188
00:08:51,130 --> 00:08:56,260
So at this point we will get two from both the sides and two plus two because over here we have one

189
00:08:56,260 --> 00:08:56,800
plus one right.

190
00:08:56,800 --> 00:09:00,610
So two plus two which is four plus one plus one will give us six.

191
00:09:00,610 --> 00:09:02,830
And that will be the maximum diameter.

192
00:09:02,830 --> 00:09:04,150
And that is what we have.

193
00:09:04,150 --> 00:09:08,470
We have seen that the function returns the function returns the maximum diameter.

194
00:09:08,470 --> 00:09:08,950
So that's how.

195
00:09:09,040 --> 00:09:11,440
Now let's just complete tracing this part.

196
00:09:11,440 --> 00:09:14,890
So for node three the left call is done.

197
00:09:14,890 --> 00:09:16,210
So this line is done.

198
00:09:16,210 --> 00:09:20,260
Now we go to the right call which will go in this direction right now.

199
00:09:20,260 --> 00:09:22,750
At this point again it will try to go left.

200
00:09:22,750 --> 00:09:25,900
And this will return minus one for this node.

201
00:09:25,900 --> 00:09:26,080
Right.

202
00:09:26,080 --> 00:09:30,100
So the height the height over here is going to be minus one.

203
00:09:30,100 --> 00:09:33,730
Because for the height of a null tree is minus one, the same thing will happen again.

204
00:09:33,730 --> 00:09:34,510
It will go right.

205
00:09:34,510 --> 00:09:36,400
So from here it will go right which.

206
00:09:36,400 --> 00:09:39,910
And then from here it will try to go left, but it will return minus one.

207
00:09:39,910 --> 00:09:44,230
Because we have seen that if the node is null, we will return minus one as the height.

208
00:09:44,230 --> 00:09:46,600
And then again from here it will go right.

209
00:09:46,600 --> 00:09:48,940
And you can see that over here it will try.

210
00:09:48,970 --> 00:09:50,860
Go left minus one will be returned.

211
00:09:50,860 --> 00:09:51,520
It will try.

212
00:09:51,550 --> 00:09:52,510
Go right again.

213
00:09:52,510 --> 00:09:53,800
Minus one will be returned.

214
00:09:53,800 --> 00:09:59,260
So the diameter would be calculated as minus one plus minus one which is minus two plus two zero.

215
00:09:59,260 --> 00:10:01,750
So the diameter of this node is equal to zero.

216
00:10:01,750 --> 00:10:06,010
And then we are going to return the maximum between these two which is minus one.

217
00:10:06,010 --> 00:10:07,720
And then we are going to add one right.

218
00:10:07,720 --> 00:10:08,710
So we are going to add one.

219
00:10:08,710 --> 00:10:10,270
So we are going to return zero.

220
00:10:10,270 --> 00:10:14,170
So over here in for for this call it's going to return zero.

221
00:10:15,260 --> 00:10:18,980
So at this node we are getting minus one and zero right.

222
00:10:18,980 --> 00:10:22,760
So again it will calculate the diameter which is not going to be greater than what's there.

223
00:10:22,760 --> 00:10:22,910
Right.

224
00:10:22,910 --> 00:10:24,470
So just let's just calculate it.

225
00:10:24,470 --> 00:10:29,060
So we get minus one plus zero which is minus one plus one plus one.

226
00:10:29,060 --> 00:10:30,200
So we get one.

227
00:10:30,200 --> 00:10:32,300
So the diameter of this node is just one.

228
00:10:32,300 --> 00:10:32,690
Right.

229
00:10:32,690 --> 00:10:37,340
And then it's going to return the height which is the greater of these two which is zero plus one.

230
00:10:37,340 --> 00:10:39,380
So from here we are going to return one.

231
00:10:39,380 --> 00:10:42,200
And again the height from here what will be the height.

232
00:10:42,200 --> 00:10:44,870
It will be the greater of these two which is minus one and one.

233
00:10:44,870 --> 00:10:46,520
The greater is one plus one.

234
00:10:46,520 --> 00:10:49,190
So that's how we are going to get back two over here as well.

235
00:10:49,190 --> 00:10:54,320
So at this node this the left gives back to the right also gives back to.

236
00:10:54,320 --> 00:10:55,400
And then we add two.

237
00:10:55,430 --> 00:10:57,800
So that's how we get six which is the diameter.

238
00:10:57,890 --> 00:10:59,900
So this function works in this way.

239
00:10:59,900 --> 00:11:04,100
And then again we have seen that over here we have the height.

240
00:11:04,100 --> 00:11:07,460
The height is the greater of these two which is two itself plus one.

241
00:11:07,460 --> 00:11:09,800
So this will return three as the height.

242
00:11:09,800 --> 00:11:12,950
And from the left side this will return zero.

243
00:11:12,950 --> 00:11:17,990
And then again at this point the diameter will be three plus zero plus two which is equal to five.

244
00:11:17,990 --> 00:11:22,250
So we can see that we have 1231234.

245
00:11:22,250 --> 00:11:24,980
And then this node right 12345.

246
00:11:24,980 --> 00:11:28,130
So that's how we get five which is the diameter through this node.

247
00:11:28,130 --> 00:11:33,590
In this way we have found that the diameter of the given binary tree is equal to six.

248
00:11:33,590 --> 00:11:38,240
Now let's take a quick look at the space and time complexity of this solution.

249
00:11:38,240 --> 00:11:40,550
Now over here we are just doing DFS.

250
00:11:40,550 --> 00:11:45,920
And we know that the time complexity of DFS is O of N, because we are just traversing through every

251
00:11:45,920 --> 00:11:46,790
node one time.

252
00:11:46,790 --> 00:11:52,040
Or you can say that we can we are we are recursively calling the DFS function once for every node.

253
00:11:52,040 --> 00:11:55,280
So the time complexity of this solution is going to be O of n.

254
00:11:55,280 --> 00:11:58,700
And the space complexity will depend on the depth of the tree.

255
00:11:58,700 --> 00:12:04,370
So the space complexity is equal to the maximum depth of the tree because this is going to be a recursive

256
00:12:04,370 --> 00:12:05,090
solution.

257
00:12:06,590 --> 00:12:10,100
Now this because we are doing Big-O analysis.

258
00:12:10,100 --> 00:12:13,190
The maximum possible depth is going to be O of N, right?

259
00:12:13,190 --> 00:12:16,340
When the given binary tree is just going to look like a linked list.

260
00:12:16,340 --> 00:12:21,470
So that's why we can say that the space complexity of this solution is also o of n.