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

2
00:00:01,580 --> 00:00:05,600
Now in this video let's try to think about how we can solve this question.

3
00:00:05,600 --> 00:00:07,670
We are given this binary tree over here.

4
00:00:07,670 --> 00:00:10,610
And we have to find the diameter of this binary tree.

5
00:00:10,610 --> 00:00:16,550
And remember we have seen that the diameter of a binary tree is the length between two nodes.

6
00:00:16,550 --> 00:00:22,700
The longest path between two nodes and the length between two nodes is defined as the number of edges

7
00:00:22,700 --> 00:00:24,260
between those two nodes.

8
00:00:24,260 --> 00:00:24,710
All right.

9
00:00:24,710 --> 00:00:30,950
Now, before we go ahead and discuss the algorithm about how we can solve this, let's make a few observations.

10
00:00:31,370 --> 00:00:35,690
Now the first observation that we make is let's for example, take this node over here.

11
00:00:35,690 --> 00:00:39,380
Now what is the diameter that passes through one?

12
00:00:39,380 --> 00:00:44,000
Or for example, we are trying to think of the longest path that passes through one.

13
00:00:44,000 --> 00:00:44,360
All right.

14
00:00:44,360 --> 00:00:48,470
So for this let's go all the way left and let's go all the way right.

15
00:00:48,470 --> 00:00:49,130
Possible.

16
00:00:49,130 --> 00:00:52,490
Now over here we are taking the nodes seven and nine.

17
00:00:52,490 --> 00:00:52,880
All right.

18
00:00:52,880 --> 00:00:59,150
So the distance between these two nodes is equal to the number of edges in the path from 7 to 9.

19
00:00:59,150 --> 00:01:01,100
So we are thinking of a diameter.

20
00:01:01,100 --> 00:01:04,550
We know that the diameter is the distance between these two nodes.

21
00:01:04,550 --> 00:01:09,110
But we can think of the same concept as the diameter passing through one.

22
00:01:09,110 --> 00:01:09,470
Right.

23
00:01:09,470 --> 00:01:16,130
So to find the diameter through one we went as far left as possible and as far right as possible.

24
00:01:16,130 --> 00:01:16,280
Right.

25
00:01:16,280 --> 00:01:18,050
So we have over here one edge.

26
00:01:18,050 --> 00:01:20,810
And in this case we have 1234 edges.

27
00:01:20,810 --> 00:01:24,980
So four plus one five would be the diameter that passes through this node.

28
00:01:24,980 --> 00:01:25,430
All right.

29
00:01:25,430 --> 00:01:29,780
So again over here this looks as if we are doing a depth first search.

30
00:01:29,780 --> 00:01:30,080
Right.

31
00:01:30,080 --> 00:01:33,980
So this must have something to do with DFS or depth first search.

32
00:01:33,980 --> 00:01:36,230
So this is the first observation that we have made.

33
00:01:36,230 --> 00:01:36,680
All right.

34
00:01:36,680 --> 00:01:41,630
Now let's try to go bottom up and find the diameter at every node.

35
00:01:41,630 --> 00:01:47,120
For example for node three we will only consider the things that are down.

36
00:01:47,120 --> 00:01:48,680
That's why we are going bottom up right.

37
00:01:48,680 --> 00:01:51,500
For example for node four we can't go anywhere down.

38
00:01:51,500 --> 00:01:54,410
So we say that the diameter through four is zero.

39
00:01:54,410 --> 00:01:58,250
Now for three we can go down here we have one and we have one over here.

40
00:01:58,250 --> 00:02:03,350
So we can say that the diameter through three is equal to one plus one which is equal to two.

41
00:02:03,350 --> 00:02:07,100
So we are going bottom up and we are finding the diameter at every node.

42
00:02:07,100 --> 00:02:08,240
So let's try to do that.

43
00:02:08,240 --> 00:02:10,790
So for these two nodes it's going to be zero right.

44
00:02:10,790 --> 00:02:13,160
Because we cannot go down any further.

45
00:02:14,040 --> 00:02:15,480
And for this node.

46
00:02:15,480 --> 00:02:21,360
For node three, for the diameter through three we can go one depth over here.

47
00:02:21,360 --> 00:02:21,570
Right.

48
00:02:21,570 --> 00:02:24,090
So we have one edge over here and we have one edge over here.

49
00:02:24,090 --> 00:02:25,140
So one plus one.

50
00:02:25,140 --> 00:02:28,740
So that gives the diameter through node three is equal to two.

51
00:02:28,740 --> 00:02:29,160
Right.

52
00:02:29,160 --> 00:02:31,890
And what about the diameter through node two.

53
00:02:31,920 --> 00:02:33,600
So we have one two over here.

54
00:02:33,600 --> 00:02:33,750
Right.

55
00:02:33,750 --> 00:02:34,800
So we have two over here.

56
00:02:34,800 --> 00:02:37,170
So we can say this is equal to two right.

57
00:02:37,170 --> 00:02:39,600
And we don't have anything to go right.

58
00:02:39,600 --> 00:02:45,810
And for the node eight for this one over here we we have one two and three and one two and three.

59
00:02:45,810 --> 00:02:51,000
So we can say that the diameter through node eight is equal to six right now.

60
00:02:51,000 --> 00:02:53,310
Similarly for this node it's zero.

61
00:02:53,310 --> 00:02:54,240
For this it's one.

62
00:02:54,240 --> 00:02:55,380
And for this it's two.

63
00:02:55,380 --> 00:02:55,800
Right.

64
00:02:55,800 --> 00:02:59,730
And then for this node over here we can go one in this direction.

65
00:02:59,730 --> 00:03:03,120
And we can go 123 and four in this direction.

66
00:03:03,120 --> 00:03:05,640
So that would be one plus four which is equal to five.

67
00:03:05,640 --> 00:03:06,090
Right.

68
00:03:06,090 --> 00:03:09,870
And then for again for this node we can't go anywhere down.

69
00:03:09,870 --> 00:03:12,540
So the diameter through that node is equal to zero.

70
00:03:12,540 --> 00:03:17,850
Now in this way by thinking of the distance between two nodes we have, we have changed the way we thought

71
00:03:17,850 --> 00:03:18,330
about it.

72
00:03:18,330 --> 00:03:24,030
And instead of that we are thinking of the diameter through a particular node by going down both left

73
00:03:24,030 --> 00:03:26,310
and right as deep as possible.

74
00:03:26,310 --> 00:03:26,640
Right.

75
00:03:26,640 --> 00:03:32,640
So in this way we have found the diameter at every particular node, so the diameter through every node.

76
00:03:32,640 --> 00:03:34,500
And then we just take the maximum right.

77
00:03:34,500 --> 00:03:38,940
So this would give us the diameter of this particular binary tree is equal to six.

78
00:03:38,940 --> 00:03:40,650
So this is the second intuition right.

79
00:03:40,650 --> 00:03:46,650
So instead of thinking instead of taking these two nodes and trying to think of the path through them,

80
00:03:46,650 --> 00:03:50,070
we are actually thinking of taking the diameter through this node.

81
00:03:50,070 --> 00:03:52,710
And then we found the diameter through every node.

82
00:03:52,710 --> 00:03:54,270
And then we just take the maximum.

83
00:03:54,270 --> 00:03:56,610
So this is how we are going to proceed with this.

84
00:03:56,610 --> 00:03:58,590
So this is the second intuition.

85
00:03:58,590 --> 00:03:58,950
All right.

86
00:03:58,980 --> 00:04:00,180
Now let's proceed.

87
00:04:00,660 --> 00:04:07,050
Now before we go ahead and think of how we can code this out or have an algorithm in a recursive manner.

88
00:04:07,050 --> 00:04:11,040
For this, let's also quickly think about the height of a node.

89
00:04:11,040 --> 00:04:11,310
All right.

90
00:04:11,310 --> 00:04:13,590
So this is something that we have discussed previously.

91
00:04:13,590 --> 00:04:16,080
But let me just quickly revise it over here.

92
00:04:16,080 --> 00:04:22,860
The height of a node is nothing but the number of edges in the longest path from that node to the leaf

93
00:04:22,860 --> 00:04:23,160
node.

94
00:04:23,160 --> 00:04:24,720
So again we are going down right.

95
00:04:24,720 --> 00:04:26,850
So from the node to the leaf node.

96
00:04:26,850 --> 00:04:27,450
All right.

97
00:04:27,480 --> 00:04:29,520
Now let's go ahead and write.

98
00:04:29,520 --> 00:04:31,650
Try to think of the height of these nodes.

99
00:04:31,650 --> 00:04:33,690
Now before that let me quickly revise.

100
00:04:33,690 --> 00:04:35,790
The height of a leaf node is equal to zero.

101
00:04:35,790 --> 00:04:36,210
Right.

102
00:04:36,210 --> 00:04:39,360
So the height of these nodes which are leaf nodes is equal to zero.

103
00:04:39,360 --> 00:04:42,810
And the height of a null tree is equal to minus one.

104
00:04:42,810 --> 00:04:43,170
All right.

105
00:04:43,170 --> 00:04:45,000
So below this you have null right.

106
00:04:45,000 --> 00:04:46,470
So you have null over here everywhere.

107
00:04:46,470 --> 00:04:50,670
So the height of those null levels is equal to minus one.

108
00:04:50,670 --> 00:04:53,340
Because the height of a null tree is equal to minus one.

109
00:04:53,340 --> 00:04:55,590
So these are two points that you need to keep in mind.

110
00:04:55,590 --> 00:04:58,800
So again these three these 41234.

111
00:04:58,800 --> 00:05:00,570
So we have four leaf nodes.

112
00:05:00,570 --> 00:05:02,670
So the height over here is going to be zero.

113
00:05:02,670 --> 00:05:03,120
All right.

114
00:05:03,120 --> 00:05:04,710
Now what's the height over here.

115
00:05:04,710 --> 00:05:06,330
And here it's going to be one.

116
00:05:06,330 --> 00:05:06,510
Right.

117
00:05:06,510 --> 00:05:08,640
So the height over here and here is equal to one.

118
00:05:08,640 --> 00:05:10,320
And what is the height over here.

119
00:05:10,320 --> 00:05:11,010
It's two right.

120
00:05:11,010 --> 00:05:11,610
It's one two.

121
00:05:11,640 --> 00:05:12,870
So the height over here is two.

122
00:05:12,870 --> 00:05:15,600
And the height over here is also equal to two.

123
00:05:16,240 --> 00:05:19,030
And what about the height over here that's going to be three.

124
00:05:19,030 --> 00:05:22,090
And again the height over here is going to be four.

125
00:05:22,090 --> 00:05:25,150
So we have just written down the height at every node.

126
00:05:25,150 --> 00:05:31,540
Now when we compare the diameter and the height at a particular node, we can develop this intuition

127
00:05:31,540 --> 00:05:37,660
that the diameter at a node is nothing but the height at the left node, plus the height at the right

128
00:05:37,660 --> 00:05:39,190
node plus one plus one.

129
00:05:39,190 --> 00:05:40,360
Let's try to understand this.

130
00:05:40,360 --> 00:05:42,550
For example, let's take this node over here.

131
00:05:42,550 --> 00:05:47,620
Now the height at the left node is zero, and the height at the life right node is equal to zero.

132
00:05:47,620 --> 00:05:51,010
And then we have one edge over here and one edge over here.

133
00:05:51,010 --> 00:05:54,130
That's why we have zero plus one and zero plus one.

134
00:05:54,130 --> 00:05:56,710
So this this plus one plus one.

135
00:05:56,710 --> 00:05:59,830
We are adding these two because we have two extra edges.

136
00:05:59,830 --> 00:06:00,130
Right.

137
00:06:00,130 --> 00:06:02,410
So that's these two edges in this case.

138
00:06:02,410 --> 00:06:09,430
So we have the diameter of this one over here is equal to two zero plus zero plus one plus one which

139
00:06:09,430 --> 00:06:10,210
gives us two.

140
00:06:10,210 --> 00:06:12,340
Now let's try a few more cases.

141
00:06:13,330 --> 00:06:15,010
What about this node over here?

142
00:06:15,010 --> 00:06:17,020
Let's try to think of this node over here.

143
00:06:17,020 --> 00:06:20,110
Now the height of the left node is equal to two.

144
00:06:20,140 --> 00:06:22,360
The height of the right node is equal to two right.

145
00:06:22,360 --> 00:06:24,820
So two plus two plus one plus one.

146
00:06:24,820 --> 00:06:26,110
So we are adding these two right.

147
00:06:26,110 --> 00:06:26,740
These two.

148
00:06:26,740 --> 00:06:29,620
And we get the diameter over here which is equal to six.

149
00:06:29,620 --> 00:06:31,900
Now we can see that mathematically this works.

150
00:06:31,900 --> 00:06:34,690
Now let's also try to think of the intuition behind this.

151
00:06:34,690 --> 00:06:39,430
Actually when we do this that is height of the left node plus height of the right node plus one plus

152
00:06:39,430 --> 00:06:39,760
one.

153
00:06:39,760 --> 00:06:41,110
What are we actually doing.

154
00:06:41,110 --> 00:06:43,660
We are just taking the diameter through that node.

155
00:06:43,660 --> 00:06:43,840
Right.

156
00:06:43,840 --> 00:06:48,070
So we are going as deep as possible left which is this much right.

157
00:06:48,070 --> 00:06:49,810
So height left plus one.

158
00:06:49,810 --> 00:06:54,520
If we add these two that's the number of edges when we go as deep left as possible.

159
00:06:54,520 --> 00:07:00,220
Now when we go as deep right as possible, we have to just take the height at the right node and then

160
00:07:00,220 --> 00:07:00,910
plus one right.

161
00:07:00,910 --> 00:07:02,380
Because we have this extra node.

162
00:07:02,380 --> 00:07:03,700
So that is what we have done.

163
00:07:03,700 --> 00:07:03,880
Right.

164
00:07:03,880 --> 00:07:09,490
So when we wanted to find the diameter at a particular node, we went as much left as possible.

165
00:07:09,490 --> 00:07:11,440
And then we go as much right as possible.

166
00:07:11,440 --> 00:07:15,910
So that is nothing but this over here height at the left node plus height at the right node.

167
00:07:15,910 --> 00:07:19,990
And then we have to add one plus one because we have these two edges over here.

168
00:07:19,990 --> 00:07:21,430
So till here we get the height.

169
00:07:21,430 --> 00:07:23,920
And then we have one over here till here we get the height.

170
00:07:23,920 --> 00:07:25,360
And then we have one more edge over here.

171
00:07:25,360 --> 00:07:30,880
So the diameter at a node is nothing but the height at the left node plus the height at the right node

172
00:07:30,880 --> 00:07:32,500
plus one plus one.

173
00:07:32,560 --> 00:07:33,070
All right.

174
00:07:33,070 --> 00:07:36,130
Now so this is how we are going to solve this question.

175
00:07:36,130 --> 00:07:36,550
All right.

176
00:07:36,550 --> 00:07:39,250
And then again remember we have null nodes over here.

177
00:07:39,250 --> 00:07:42,160
And the height at null nodes is equal to minus one.

178
00:07:42,160 --> 00:07:47,170
So that is going to be our base case in the recursive solution that we are going to come up with.

179
00:07:47,170 --> 00:07:47,650
All right.

180
00:07:47,650 --> 00:07:48,880
So now let's proceed.

181
00:07:48,880 --> 00:07:50,530
So let's try to go bottom up.

182
00:07:50,530 --> 00:07:54,460
And then so we will have a recursive call recursive function.

183
00:07:54,460 --> 00:07:55,840
So we will come till here.

184
00:07:55,840 --> 00:07:57,100
And when we come over here.

185
00:07:57,100 --> 00:07:59,830
And then we will go to its child which is null.

186
00:07:59,830 --> 00:08:01,660
And then it will start returning.

187
00:08:01,660 --> 00:08:03,820
So we will get minus one back from here.

188
00:08:03,820 --> 00:08:04,180
All right.

189
00:08:04,180 --> 00:08:06,250
So this is the intuition behind this solution.

190
00:08:06,250 --> 00:08:10,720
So we will try to use this to come up with an algorithm to solve this question.

191
00:08:10,720 --> 00:08:15,040
Now let's proceed and try to think of a solution in terms of the algorithm.

192
00:08:15,040 --> 00:08:17,410
And remember when it comes to height right.

193
00:08:17,410 --> 00:08:22,870
For for this to be able for us to be able to code this, we need a way to find the height at a particular

194
00:08:22,870 --> 00:08:29,500
node and the height at a node at a particular node is nothing but the maximum between the height at

195
00:08:29,500 --> 00:08:31,420
its left and right node, plus one right.

196
00:08:31,420 --> 00:08:34,360
For example, if you want to know the height at this node, right?

197
00:08:34,360 --> 00:08:39,100
So we just need to know the height the of the left node over here that's two.

198
00:08:39,100 --> 00:08:41,350
And the height at the right node which is two.

199
00:08:41,380 --> 00:08:44,320
So we take the maximum between these two and we add one.

200
00:08:44,320 --> 00:08:47,830
For example if this was something like this we have eight.

201
00:08:47,830 --> 00:08:50,500
Then we have let's say one we have two.

202
00:08:50,500 --> 00:08:52,240
And let's say we have three over here.

203
00:08:52,240 --> 00:08:53,950
And then we have four over here.

204
00:08:53,950 --> 00:08:56,500
So the height over here is zero one and two.

205
00:08:56,500 --> 00:08:58,480
And the height over here is zero right.

206
00:08:58,480 --> 00:09:03,580
So if you want to know the height at this particular node we just need to take the maximum between these

207
00:09:03,580 --> 00:09:04,630
two which is equal to two.

208
00:09:04,630 --> 00:09:07,450
And then we have to add one because we are going one level up right.

209
00:09:07,450 --> 00:09:11,590
So the height at this node will be just equal to two plus one which is equal to three.

210
00:09:11,590 --> 00:09:16,270
So this is also something that we will use so that we can get the height at a particular node.

211
00:09:16,270 --> 00:09:16,780
All right.

212
00:09:16,780 --> 00:09:23,470
So let's now try to implement this solution using the intuition that we have developed over here.

213
00:09:23,470 --> 00:09:23,740
All right.

214
00:09:23,740 --> 00:09:29,380
So the diameter at a particular node is height at the left node plus height at its right child plus

215
00:09:29,380 --> 00:09:30,280
one plus one.

216
00:09:30,280 --> 00:09:32,800
And then we just need to find the maximum diameter.

217
00:09:32,800 --> 00:09:38,800
And instead of thinking about the path between two nodes, we are just thinking of the diameter through

218
00:09:38,800 --> 00:09:45,400
a node by going as much left as possible and as much right as possible, which is nothing but DFS or

219
00:09:45,400 --> 00:09:45,670
depth.

220
00:09:45,670 --> 00:09:46,270
First search.

221
00:09:46,270 --> 00:09:46,780
All right.

222
00:09:46,780 --> 00:09:48,850
So let's go ahead and write a function.

223
00:09:48,850 --> 00:09:50,320
And let's just call it DFS.

224
00:09:50,980 --> 00:09:56,020
Now if we encounter a node which is null then we will just return minus one.

225
00:09:56,020 --> 00:09:59,470
So that is going to be our base case in our recursive solution.

226
00:09:59,470 --> 00:10:05,770
And that is what will happen at this place right when we when we call the recursive call recursive function.

227
00:10:05,770 --> 00:10:10,870
And when we get to the null node over here it will return minus one and then it will start returning.

228
00:10:10,870 --> 00:10:12,160
So this is the base case.

229
00:10:12,160 --> 00:10:15,280
And this DFS function is going to return the height.

230
00:10:15,280 --> 00:10:15,610
Right.

231
00:10:15,610 --> 00:10:20,950
Because at every point we want to get the height back so that we can find the diameter at that particular

232
00:10:20,950 --> 00:10:21,340
node.

233
00:10:21,340 --> 00:10:21,700
Right.

234
00:10:21,700 --> 00:10:23,920
So this is also going to return the height.

235
00:10:23,920 --> 00:10:30,640
And the height of a particular node is the maximum of the left height and right height plus one.

236
00:10:30,640 --> 00:10:31,570
So we have seen that.

237
00:10:31,570 --> 00:10:33,370
So this is what this function will return.

238
00:10:33,370 --> 00:10:33,820
All right.

239
00:10:33,820 --> 00:10:38,890
Now inside this function what we will do is we have we have called this function for a particular node.

240
00:10:38,890 --> 00:10:39,280
Right.

241
00:10:39,280 --> 00:10:45,220
So now we will try to find the height of its left child and right child.

242
00:10:45,220 --> 00:10:45,610
All right.

243
00:10:45,610 --> 00:10:50,890
So for this we will call this function recursively passing in the left child and the right child.

244
00:10:50,890 --> 00:10:55,120
So we get the height at the left child and the height at the right child.

245
00:10:55,120 --> 00:10:57,010
And then we are just going to implement this.

246
00:10:57,010 --> 00:11:00,400
The diameter is going to be the sum of these plus one plus one.

247
00:11:00,400 --> 00:11:06,370
So diameter of that particular node is LH left height plus right height plus one plus one.

248
00:11:06,370 --> 00:11:07,750
So we get the diameter.

249
00:11:07,750 --> 00:11:12,190
Then we need to check with the we need to have a global variable.

250
00:11:12,190 --> 00:11:12,730
Let's just call it.

251
00:11:12,910 --> 00:11:13,840
Max diameter.

252
00:11:13,930 --> 00:11:14,410
All right.

253
00:11:14,410 --> 00:11:16,060
Which we will initialize to zero.

254
00:11:16,060 --> 00:11:21,880
And then whenever we calculate a diameter, we will compare that particular diameter with the value

255
00:11:21,880 --> 00:11:23,350
that we have in max diameter.

256
00:11:23,350 --> 00:11:27,940
So among these whichever is maximum that would be allocated to max diameter.

257
00:11:27,940 --> 00:11:30,790
So in this way we will store the maximum diameter.

258
00:11:30,790 --> 00:11:31,330
All right.

259
00:11:31,330 --> 00:11:36,820
And then in this function we will just return the height of that particular node.

260
00:11:36,820 --> 00:11:38,410
So this is how we are going to solve it.

261
00:11:38,410 --> 00:11:44,020
And then finally when we are out of the function we will just return the maximum diameter because that

262
00:11:44,020 --> 00:11:45,220
is what we need to find.

263
00:11:45,220 --> 00:11:46,210
So let's proceed.

264
00:11:46,210 --> 00:11:48,760
So we have seen how we are going to solve this question.

265
00:11:48,760 --> 00:11:53,290
Now initially we will call this recursive function and we will pass the root.

266
00:11:53,290 --> 00:11:55,060
So we will say DFS at root.

267
00:11:55,060 --> 00:11:58,690
So we are calling the DFS function and we are passing the parameter root.

268
00:11:58,690 --> 00:11:58,990
All right.

269
00:11:58,990 --> 00:11:59,860
So we are over here.

270
00:11:59,860 --> 00:12:02,710
Now inside this function we will check if this is null.

271
00:12:02,710 --> 00:12:03,970
No this is not null.

272
00:12:03,970 --> 00:12:10,720
So at this place we will call the DFS function recursively passing in the left node which is seven.

273
00:12:10,720 --> 00:12:10,990
All right.

274
00:12:10,990 --> 00:12:12,010
So this one over here.

275
00:12:12,010 --> 00:12:15,490
Now again we are we are going to come inside this function.

276
00:12:15,490 --> 00:12:17,080
We will see that this is not null.

277
00:12:17,080 --> 00:12:19,480
So again we are going to call it for the left node.

278
00:12:19,480 --> 00:12:21,910
And at this point we will see that it is null.

279
00:12:21,910 --> 00:12:23,890
And hence this will return minus one.

280
00:12:23,890 --> 00:12:26,650
So we get minus one minus one over here.

281
00:12:26,650 --> 00:12:29,710
And similarly over here also we are going to get minus one right.

282
00:12:29,710 --> 00:12:31,990
The right side also is going to return minus one.

283
00:12:31,990 --> 00:12:38,860
So when we called the function with node seven its left height is minus one, its right height is minus

284
00:12:38,860 --> 00:12:39,220
one.

285
00:12:39,220 --> 00:12:45,250
And then the diameter at this particular node will be minus one plus minus one plus one plus one which

286
00:12:45,250 --> 00:12:46,180
is equal to zero right.

287
00:12:46,180 --> 00:12:48,850
So max diameter is equal to zero.

288
00:12:48,850 --> 00:12:50,980
Initially we will initialize this to zero.

289
00:12:50,980 --> 00:12:54,370
And at this point we calculate that the diameter is zero.

290
00:12:54,370 --> 00:12:55,960
But over here also we have zero.

291
00:12:55,960 --> 00:12:58,360
So we we do not need to overwrite this.

292
00:12:58,360 --> 00:12:58,810
All right.

293
00:12:58,810 --> 00:12:59,980
And then we proceed.

294
00:12:59,980 --> 00:13:00,190
Right.

295
00:13:00,190 --> 00:13:01,180
So this is done.

296
00:13:01,180 --> 00:13:06,190
Now this was part of this left call right where we called the DFS function with node one.

297
00:13:06,190 --> 00:13:08,140
So the left call will return right.

298
00:13:08,140 --> 00:13:13,060
So the left call will return the maximum between these two which is minus one itself.

299
00:13:13,060 --> 00:13:13,630
Plus one.

300
00:13:13,630 --> 00:13:16,990
So over here we will get back the height of this which is equal to zero.

301
00:13:16,990 --> 00:13:18,340
So this will return zero.

302
00:13:18,340 --> 00:13:18,790
All right.

303
00:13:18,790 --> 00:13:20,470
So that's part of the left call.

304
00:13:21,070 --> 00:13:24,400
Now we will do the right call which is this one over here for node one.

305
00:13:24,400 --> 00:13:25,660
So this will come over here.

306
00:13:25,660 --> 00:13:28,270
And then from there it will go left all the way down.

307
00:13:28,270 --> 00:13:31,720
And then when it comes over here it will return minus one right.

308
00:13:31,720 --> 00:13:32,830
Minus one minus one.

309
00:13:32,830 --> 00:13:34,810
And again from here we will return zero.

310
00:13:34,840 --> 00:13:36,220
The same thing what we did over here.

311
00:13:36,220 --> 00:13:37,810
So over here it will return zero.

312
00:13:37,810 --> 00:13:41,950
And then from here also it will return zero because again this will return minus one.

313
00:13:41,950 --> 00:13:43,390
This will return minus one.

314
00:13:43,390 --> 00:13:47,320
And then the height of this will be the maximum between these two plus one.

315
00:13:47,320 --> 00:13:47,500
Right.

316
00:13:47,500 --> 00:13:48,790
So this will return zero.

317
00:13:48,790 --> 00:13:53,470
So at this node we are going to get left height as zero and right height as as zero.

318
00:13:53,470 --> 00:13:57,700
And then the diameter will be calculated as zero plus zero plus one plus one.

319
00:13:57,700 --> 00:13:59,680
So we get that the diameter is equal to two.

320
00:13:59,680 --> 00:14:05,710
And that will overwrite what we have already in max diameter because two is greater than zero.

321
00:14:05,710 --> 00:14:06,940
So we get two over here.

322
00:14:06,940 --> 00:14:07,480
All right.

323
00:14:07,480 --> 00:14:12,460
So again from here we will return its height which is the maximum between these two plus one.

324
00:14:12,460 --> 00:14:13,690
So we will return one.

325
00:14:13,690 --> 00:14:16,450
And then over here we will return minus one because we have null.

326
00:14:16,450 --> 00:14:21,970
Now again let's calculate the diameter over here one plus minus one which is zero plus one plus one.

327
00:14:21,970 --> 00:14:24,100
So the diameter through two.

328
00:14:24,130 --> 00:14:25,510
This node over here is equal to two.

329
00:14:25,540 --> 00:14:26,830
So we don't need to overwrite.

330
00:14:26,830 --> 00:14:31,060
And again from here we are going to return its height which is one plus one which is two.

331
00:14:31,060 --> 00:14:31,240
Right.

332
00:14:31,240 --> 00:14:32,530
So this will return two.

333
00:14:32,530 --> 00:14:38,170
And that's how similarly from this part also you can see that again the height over here is also going

334
00:14:38,170 --> 00:14:38,620
to be two.

335
00:14:38,620 --> 00:14:38,800
Right.

336
00:14:38,800 --> 00:14:40,870
So this also will return two.

337
00:14:40,870 --> 00:14:46,690
And at this node when the left and right come back we will have two plus two plus one plus one which

338
00:14:46,690 --> 00:14:47,530
is equal to six.

339
00:14:47,530 --> 00:14:52,480
So that's how the maximum diameter will be calculated which is equal to six.

340
00:14:52,480 --> 00:14:54,490
Again let's just trace this back.

341
00:14:54,490 --> 00:14:57,280
You can see how it works first before it comes back.

342
00:14:57,280 --> 00:14:58,750
It will go all the way down right.

343
00:14:58,750 --> 00:14:59,830
It will go away this way.

344
00:14:59,830 --> 00:15:03,190
Then it will try to go left but it will return minus one.

345
00:15:03,190 --> 00:15:05,530
Then it will try to go right again.

346
00:15:05,530 --> 00:15:06,490
It will try to go left.

347
00:15:06,490 --> 00:15:08,230
This will return minus one again.

348
00:15:08,230 --> 00:15:09,400
It will try to go right.

349
00:15:09,400 --> 00:15:12,400
It will then try to go left which will return minus one.

350
00:15:12,400 --> 00:15:14,380
And from here also you get minus one.

351
00:15:14,380 --> 00:15:17,770
And you calculate the diameter over here which is going to be zero.

352
00:15:17,770 --> 00:15:20,890
And then you return the height which is equal to zero right.

353
00:15:20,890 --> 00:15:22,420
So from here you get back zero.

354
00:15:22,420 --> 00:15:25,150
And this part over here gives back minus one.

355
00:15:25,150 --> 00:15:28,330
So among these two the greater is zero plus one.

356
00:15:28,330 --> 00:15:29,980
So over here we are going to return one.

357
00:15:29,980 --> 00:15:32,380
And again you have minus one over here one over here.

358
00:15:32,410 --> 00:15:35,080
The greater of these two is one and one plus one.

359
00:15:35,080 --> 00:15:36,670
That's how you return two over here.

360
00:15:36,670 --> 00:15:38,290
And that is how this function works.

361
00:15:38,290 --> 00:15:43,150
And that's how we calculate the maximum diameter of the given binary tree.

362
00:15:43,930 --> 00:15:44,320
All right.

363
00:15:44,320 --> 00:15:48,250
Now let's quickly look at the complexity analysis of this solution.

364
00:15:48,250 --> 00:15:52,810
The time complexity of this solution is going to be O of N because we are just doing depth.

365
00:15:52,810 --> 00:15:53,620
First search over here.

366
00:15:53,620 --> 00:15:53,890
Right.

367
00:15:53,890 --> 00:15:58,390
And we have seen previously that the time complexity of DFS is nothing but O of N.

368
00:15:58,390 --> 00:16:00,040
You can also think of it in this way.

369
00:16:00,040 --> 00:16:04,120
We are just calling the DFS function on every node one time, right.

370
00:16:04,120 --> 00:16:06,220
So again that's n number of calls.

371
00:16:06,220 --> 00:16:09,220
And we are just traversing every node one time.

372
00:16:09,220 --> 00:16:12,550
That's why the time complexity of this solution is O of n.

373
00:16:12,550 --> 00:16:14,530
Now what about the space complexity.

374
00:16:14,560 --> 00:16:16,870
Now this is a recursive solution.

375
00:16:16,870 --> 00:16:20,170
So there will be space used up in the call stack.

376
00:16:20,170 --> 00:16:25,240
So that's why we can say that the worst case space complexity is going to be O of n.

377
00:16:25,240 --> 00:16:28,630
So this will happen when the given tree is not balanced right.

378
00:16:28,630 --> 00:16:34,060
So when the tree is not balanced the height is going to be o of n, the height is going to be n if it

379
00:16:34,060 --> 00:16:35,050
looks like a linked list.

380
00:16:35,050 --> 00:16:35,410
Right.

381
00:16:35,410 --> 00:16:37,330
So that's the worst case possibility.

382
00:16:37,330 --> 00:16:42,820
So if the tree looks looks like just a link list, in this case the height is going to be n.

383
00:16:42,820 --> 00:16:48,880
Otherwise if it's a balanced tree, we can say that the space complexity is going to be O of the maximum

384
00:16:48,880 --> 00:16:53,620
depth or the height, because that's going to be the maximum number of calls which are there in the

385
00:16:53,620 --> 00:16:55,210
call stack at the same time.