3439. Find Minimum Diameter After Merging Two Trees
My accepted Python solution to LeetCode problem 3439, Find Minimum Diameter After Merging Two Trees, running in 525ms.
- Difficulty: Hard
- Python
- Runtime 525ms
- Memory 79.3MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 525ms, memory 79.3MB, accepted 2026-01-01.
class Solution:
def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
def get_diameter(edges, n):
if n == 1:
return 0
from collections import defaultdict, deque
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# BFS to find furthest node from any starting node
def bfs(start):
visited = {start}
queue = deque([(start, 0)])
furthest_node, max_dist = start, 0
while queue:
node, dist = queue.popleft()
if dist > max_dist:
max_dist = dist
furthest_node = node
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return furthest_node, max_dist
# Find one end of diameter
end1, _ = bfs(0)
# Find other end and diameter
end2, diameter = bfs(end1)
return diameter
n1 = len(edges1) + 1
n2 = len(edges2) + 1
d1 = get_diameter(edges1, n1)
d2 = get_diameter(edges2, n2)
# When connecting the trees, the new diameter is max of:
# 1. d1 (diameter of tree1)
# 2. d2 (diameter of tree2)
# 3. ceil(d1/2) + ceil(d2/2) + 1 (connecting through centers)
radius1 = (d1 + 1) // 2
radius2 = (d2 + 1) // 2
return max(d1, d2, radius1 + radius2 + 1)