# 1245 Tree Diameter

The diameter of a tree is the number of edges in the longest path in that tree.

There is an undirected tree of `n` nodes labeled from `0` to `n - 1`. You are given a 2D array `edges` where `edges.length == n - 1` and `edges[i] = [ai, bi]` indicates that there is an undirected edge between nodes `ai` and `bi` in the tree.

Return the diameter of the tree.

Example 1:

``````  0
/ \
2   1

Input: edges = [[0,1],[0,2]]
Output: 2
Explanation: The longest path of the tree is the path 1 - 0 - 2.
``````

Example 2:

``````   1
/ | \
0  2  4
|  |
3  5

Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
Output: 4
Explanation: The longest path of the tree is the path 3 - 2 - 1 - 4 - 5.
``````

Constraints:

• `n == edges.length + 1`
• `1 <= n <= 104`
• `0 <= ai, bi < n`
• `ai != bi`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 `````` ``````''' DFS ''' from collections import defaultdict class Solution: def treeDiameter(self, edges: List[List[int]]) -> int: graph = defaultdict(list) for s, d in edges: graph[s].append(d) graph[d].append(s) def dfs(node: int) -> int: top_dis1, top_dis2 = 0, 0 visited.add(node) dis = 0 for c in graph[node]: if c not in visited: dis = 1 + dfs(c) if dis > top_dis1: top_dis1, top_dis2 = dis, top_dis1 elif dis > top_dis2: top_dis2 = dis self.diameter = max(self.diameter, top_dis1 + top_dis2) return top_dis1 self.diameter = 0 visited = set() dfs(0) return self.diameter ''' 2-time BFS ''' class Solution: def treeDiameter(self, edges: List[List[int]]) -> int: graph = defaultdict(list) for s, d in edges: graph[s].append(d) graph[d].append(s) def bfs(node: int) -> Tuple[int, int]: visited = set([node]) last_node = -1 dis = -1 q = [node] while q: temp_q = [] for n in q: for child in graph[n]: if child not in visited: visited.add(child) temp_q.append(child) last_node = child dis += 1 q = temp_q return last_node, dis far_node_1, dis_1 = bfs(0) far_node_2, dis_2 = bfs(far_node_1) return dis_2``````