1
00:00:00,860 --> 00:00:01,700
Hi everyone.

2
00:00:01,700 --> 00:00:03,170
Let's do this question.

3
00:00:03,170 --> 00:00:09,800
Write a function which takes in the root of a binary tree and returns the length of the diameter of

4
00:00:09,800 --> 00:00:10,430
the tree.

5
00:00:10,430 --> 00:00:16,850
The diameter of a binary tree is the length of the longest path between any two nodes in the tree.

6
00:00:16,850 --> 00:00:20,990
It is not necessary for this path to pass through the root of the tree.

7
00:00:20,990 --> 00:00:25,670
The length of a path between two nodes is the number of edges between them.

8
00:00:25,670 --> 00:00:26,090
All right.

9
00:00:26,090 --> 00:00:28,250
So let's go ahead and try to understand this question.

10
00:00:28,250 --> 00:00:30,380
We have to find the diameter of a tree.

11
00:00:30,380 --> 00:00:35,990
And over here it's mentioned that the diameter of a binary tree is the length of the longest path between

12
00:00:35,990 --> 00:00:37,640
any two nodes in the tree.

13
00:00:37,640 --> 00:00:40,370
Now for example, we have this binary tree over here.

14
00:00:40,370 --> 00:00:45,140
Let's try to understand the length between these two nodes which are part of the binary tree.

15
00:00:45,140 --> 00:00:50,360
Now it's defined over here that the length of a path between two nodes is the number of edges between

16
00:00:50,360 --> 00:00:50,690
them.

17
00:00:50,690 --> 00:00:53,960
So let's count the number of edges between these two nodes.

18
00:00:53,960 --> 00:00:59,270
So we can see there are six nodes six edges right one, two, three, four, five and six.

19
00:00:59,270 --> 00:01:01,760
So there are six edges between these two nodes.

20
00:01:01,760 --> 00:01:08,930
And you can see that in this binary tree the longest path between two nodes is this path which which

21
00:01:08,930 --> 00:01:10,310
has six edges between it.

22
00:01:10,310 --> 00:01:14,720
That's why the diameter of this binary tree over here is equal to six.

23
00:01:14,720 --> 00:01:20,060
For example, if you take this node and this node so you can see that it just has one and two two edges

24
00:01:20,060 --> 00:01:20,750
between them.

25
00:01:20,750 --> 00:01:23,180
Or let's take this node and this node.

26
00:01:23,180 --> 00:01:25,910
So 12345.

27
00:01:25,910 --> 00:01:27,980
So there are five edges between these two.

28
00:01:27,980 --> 00:01:30,920
Or let's take the nodes this one and this one.

29
00:01:30,920 --> 00:01:35,480
So between these 21234 and five five edges are there.

30
00:01:35,480 --> 00:01:38,630
So between these two nodes there are six edges.

31
00:01:38,630 --> 00:01:40,370
So this is the longest path.

32
00:01:40,370 --> 00:01:44,510
And hence the diameter of this binary tree over here is equal to six.

33
00:01:44,510 --> 00:01:48,680
Now we have to write a function which will take in the root of a binary tree.

34
00:01:48,680 --> 00:01:52,220
And then it has to return the diameter of that particular binary tree.

35
00:01:52,220 --> 00:01:53,450
So this is the question.

36
00:01:53,450 --> 00:01:56,090
Now let's go ahead and write a few test cases.

37
00:01:56,570 --> 00:02:01,760
Now remember in the interview if you have any clarifying questions you have to ensure that you ask them

38
00:02:01,760 --> 00:02:02,660
to your interviewer.

39
00:02:02,660 --> 00:02:04,550
Now over here because it's pretty straightforward.

40
00:02:04,550 --> 00:02:07,940
Let's proceed and take a look at a few test cases.

41
00:02:07,940 --> 00:02:12,050
Now in the interview, remember, you can also come up with the test cases together with you with your

42
00:02:12,050 --> 00:02:12,650
interviewer.

43
00:02:12,650 --> 00:02:16,880
You can ask him or her whether it's okay if you together come up with test cases.

44
00:02:16,880 --> 00:02:22,310
So this will ensure that you have a very good understanding of the question and what the expectation

45
00:02:22,310 --> 00:02:25,220
is, or the expectation about the output is.

46
00:02:25,220 --> 00:02:25,670
All right.

47
00:02:25,700 --> 00:02:28,550
Now let's say this is the binary tree which is given to you.

48
00:02:28,550 --> 00:02:32,690
Now you can see that the longest path is between 4 and 8, right.

49
00:02:32,690 --> 00:02:36,200
And you have four edges between these two nodes.

50
00:02:36,200 --> 00:02:38,150
So the diameter over here has to be four.

51
00:02:38,150 --> 00:02:41,660
Right now if you take any two other nodes for example, you take this one.

52
00:02:41,660 --> 00:02:44,060
And this one there would be one two and three.

53
00:02:44,060 --> 00:02:46,640
So between these two nodes there are three edges.

54
00:02:46,640 --> 00:02:49,910
So again the longest path is between these two nodes.

55
00:02:49,910 --> 00:02:53,810
And that's why the diameter of this binary tree over here is equal to four.

56
00:02:53,810 --> 00:02:57,980
Now for this binary tree we have already seen that the diameter is equal to six.

57
00:02:57,980 --> 00:03:01,160
And in this case the two edges.

58
00:03:01,160 --> 00:03:03,080
We are considering is this one and this one.

59
00:03:03,080 --> 00:03:07,400
And if you are just given a binary tree with only one node, right.

60
00:03:07,400 --> 00:03:12,860
So in this case the diameter is going to be zero because you don't have any edge between two nodes.

61
00:03:12,860 --> 00:03:18,140
And even if the binary tree is just null in that case also we will return zero.

62
00:03:18,140 --> 00:03:18,530
All right.

63
00:03:18,530 --> 00:03:23,180
So again over here also you don't have any two nodes between which you have edges.

64
00:03:23,180 --> 00:03:25,610
So that's why we will return zero here as well.

65
00:03:25,610 --> 00:03:26,060
All right.

66
00:03:26,060 --> 00:03:30,560
So we have understood the question and we have looked at a few test cases in the next video.

67
00:03:30,560 --> 00:03:33,470
Let's try to think about how we can implement this.

68
00:03:33,470 --> 00:03:36,470
And let's try to think about the algorithm we can use for this.