## # 1245. Tree Diameter

Given an undirected tree, return its diameter: the number of edges in a longest path in that tree.

The tree is given as an array of edges where `edges[i] = [u, v]` is a bidirectional edge between nodes u and v. Each node has labels in the set `{0, 1, ..., edges.length}`.

Example 1:

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

Example 2:

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

### # Solution

Approach 1: two dfs -- start dfs from a random node, then start dfs on an endpoint of the first dfs.

Approach 2: 1 dfs and along the way, find the sum of top 2 lengths through any node.

### # Code (Python)

Approach 1:

``````    def treeDiameter(self, edges: List[List[int]]) -> int:
# idea: two dfs -- start dfs from a random node, then start dfs on an endpoint of the first dfs
neighbors = {i: [] for i in range(len(edges) + 1)}
for edge in edges:
neighbors[edge].append(edge)
neighbors[edge].append(edge)

def dfs(node, neighbors):
max_info = (0, node) # (length/steps so far, node)
stack = [(node, None, 0)]
while stack:
node, prev, level = stack.pop()
if level > max_info:
max_info = (level, node)
for neighbor in neighbors[node]:
if neighbor != prev:
stack.append((neighbor, node, level + 1))
return max_info

_, node = dfs(0, neighbors)
return dfs(node, neighbors)
``````

Approach 2:

``````    def treeDiameter(self, edges: List[List[int]]) -> int:
# idea: 1 dfs and find the sum of top 2 lengths through any node
neighbors = {i: [] for i in range(len(edges) + 1)}
for edge in edges:
neighbors[edge].append(edge)
neighbors[edge].append(edge)

result =  # record sum of top 2 lengths through any node
self._top_length(0, -1, neighbors, result)
return result

def _top_length(self, node, parent, neighbors, result):
top_two = (0, 0) # max 2 lengths starting from this node
for neighbor in neighbors[node]:
if neighbor != parent:
max_length = self._top_length(neighbor, node, neighbors, result)
if max_length > top_two:
top_two = (max_length, top_two)
elif max_length > top_two:
top_two = (top_two, max_length)
result = max(result, sum(top_two))
return top_two + 1 # plus 1 for the step from parent to current node

#################################
# OR not keeping a global variable
def treeDiameter(self, edges: List[List[int]]) -> int:
# idea: 1 dfs and find the sum of top 2 lengths through any node
neighbors = {i: [] for i in range(len(edges) + 1)}
for edge in edges:
neighbors[edge].append(edge)
neighbors[edge].append(edge)

return self._top_length(0, -1, neighbors)

def _top_length(self, node, parent, neighbors):
global_max = 0 # sum of top 2 lengths through any node
top_two = (0, 0) # max 2 lengths starting from this node
for neighbor in neighbors[node]:
if neighbor != parent:
max_seen, max_length = self._top_length(neighbor, node, neighbors)
if max_length > top_two:
top_two = (max_length, top_two)
elif max_length > top_two:
top_two = (top_two, max_length)
global_max = max(max_seen, sum(top_two), global_max)
return global_max, top_two + 1
``````

Approach 1:

Approach 2: