Find Minimum Diameter After Merging Two Trees
Problem
You are given two undirected trees, described by edge lists edges1 (n nodes) and edges2 (m nodes). Add exactly one edge connecting some node of tree 1 to some node of tree 2. Return the minimum possible diameter of the merged tree, where the diameter is the length of the longest path between any two nodes.
The merged diameter is the largest of three things: the diameter d1 of tree 1, the diameter d2 of tree 2, and a path that crosses the new edge. Connecting the centers of the two trees minimizes that crossing path, giving ⌈d1/2⌉ + ⌈d2/2⌉ + 1.
edges1 = [[0,1],[0,2],[0,3]], edges2 = [[0,1]]3from collections import deque
def minimumDiameterAfterMerge(edges1, edges2):
def diameter(edges, n):
if n <= 1:
return 0
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
def bfs(src): # farthest node + its distance
dist = [-1] * n
dist[src] = 0
far = src
q = deque([src])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
if dist[v] > dist[far]:
far = v
q.append(v)
return far, dist
u, _ = bfs(0) # one endpoint of a diameter
w, dist = bfs(u) # the opposite endpoint
return dist[w]
d1 = diameter(edges1, len(edges1) + 1)
d2 = diameter(edges2, len(edges2) + 1)
cross = (d1 + 1) // 2 + (d2 + 1) // 2 + 1
return max(d1, d2, cross)function minimumDiameterAfterMerge(edges1, edges2) {
function diameter(edges, n) {
if (n <= 1) return 0;
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
function bfs(src) { // farthest node + its distance
const dist = new Array(n).fill(-1);
dist[src] = 0;
let far = src;
const q = [src];
for (let h = 0; h < q.length; h++) {
const u = q[h];
for (const v of adj[u]) {
if (dist[v] === -1) {
dist[v] = dist[u] + 1;
if (dist[v] > dist[far]) far = v;
q.push(v);
}
}
}
return [far, dist];
}
const [u] = bfs(0); // one endpoint of a diameter
const [w, dist] = bfs(u); // the opposite endpoint
return dist[w];
}
const d1 = diameter(edges1, edges1.length + 1);
const d2 = diameter(edges2, edges2.length + 1);
const cross = ((d1 + 1) >> 1) + ((d2 + 1) >> 1) + 1;
return Math.max(d1, d2, cross);
}int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
int d1 = diameter(edges1, edges1.length + 1);
int d2 = diameter(edges2, edges2.length + 1);
int cross = (d1 + 1) / 2 + (d2 + 1) / 2 + 1;
return Math.max(Math.max(d1, d2), cross);
}
int diameter(int[][] edges, int n) {
if (n <= 1) return 0;
List<Integer>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
int[] r1 = bfs(0, adj, n); // one endpoint of a diameter
int[] r2 = bfs(r1[0], adj, n); // the opposite endpoint
return r2[1]; // {farthest node, its distance}
}
int[] bfs(int src, List<Integer>[] adj, int n) {
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[src] = 0;
int far = src;
Deque<Integer> q = new ArrayDeque<>();
q.add(src);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj[u]) if (dist[v] == -1) {
dist[v] = dist[u] + 1;
if (dist[v] > dist[far]) far = v;
q.add(v);
}
}
return new int[]{far, dist[far]};
}int bfs(int src, vector<vector<int>>& adj, int n) {
vector<int> dist(n, -1);
dist[src] = 0;
int far = src;
queue<int> q; q.push(src);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) if (dist[v] == -1) {
dist[v] = dist[u] + 1;
if (dist[v] > dist[far]) far = v;
q.push(v);
}
}
return dist[far]; // distance to farthest node
}
int diameter(vector<vector<int>>& edges, int n) {
if (n <= 1) return 0;
vector<vector<int>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
// farthest node from 0, then farthest from that node = diameter
int far = 0, best = -1;
vector<int> d(n, -1); d[0] = 0;
queue<int> q; q.push(0);
while (!q.empty()) { int u = q.front(); q.pop();
for (int v : adj[u]) if (d[v] == -1) { d[v] = d[u] + 1;
if (d[v] > best) { best = d[v]; far = v; } q.push(v); } }
return bfs(far, adj, n);
}
int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
int d1 = diameter(edges1, edges1.size() + 1);
int d2 = diameter(edges2, edges2.size() + 1);
int cross = (d1 + 1) / 2 + (d2 + 1) / 2 + 1;
return max({d1, d2, cross});
}Explanation
After adding the connecting edge, the merged tree's diameter (longest path) can fall into one of three cases. Either the longest path stays entirely inside tree 1 (length d1), entirely inside tree 2 (length d2), or it crosses the new edge. The answer is the maximum of these three, and only the crossing case depends on which nodes we connect.
A crossing path goes from some node in tree 1, into the connection node a, across the new edge to b, then out to some node in tree 2. Its length is (longest path from a inside tree 1) + 1 + (longest path from b inside tree 2). To make this as small as possible, pick a and b so the longest reach into each tree is minimized — that node is exactly the tree's center, and the longest reach from the center is the radius ⌈d/2⌉.
So the crossing length becomes ⌈d1/2⌉ + ⌈d2/2⌉ + 1, and the final answer is max(d1, d2, ⌈d1/2⌉ + ⌈d2/2⌉ + 1). We never actually have to try every pair of nodes.
Computing a tree's diameter uses the classic double-BFS trick: BFS from any node to find the farthest node u (one endpoint of a diameter), then BFS again from u; the farthest distance found is the diameter. Each BFS is linear, so the whole algorithm is linear in the number of nodes.
Example: tree 1 [[0,1],[0,2],[0,3]] is a star with diameter 2; tree 2 [[0,1]] is a single edge with diameter 1. The crossing length is ⌈2/2⌉ + ⌈1/2⌉ + 1 = 1 + 1 + 1 = 3, which dominates, so the answer is 3.