# 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[0]].append(edge[1])
neighbors[edge[1]].append(edge[0])
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[0]:
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)[0]
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[0]].append(edge[1])
neighbors[edge[1]].append(edge[0])
result = [0] # record sum of top 2 lengths through any node
self._top_length(0, -1, neighbors, result)
return result[0]
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[0]:
top_two = (max_length, top_two[0])
elif max_length > top_two[1]:
top_two = (top_two[0], max_length)
result[0] = max(result[0], sum(top_two))
return top_two[0] + 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[0]].append(edge[1])
neighbors[edge[1]].append(edge[0])
return self._top_length(0, -1, neighbors)[0]
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[0]:
top_two = (max_length, top_two[0])
elif max_length > top_two[1]:
top_two = (top_two[0], max_length)
global_max = max(max_seen, sum(top_two), global_max)
return global_max, top_two[0] + 1
# Code (C++)
Approach 1:
Approach 2: