⚡Flashcard Drill➔
NeetCode #651LC-3203HardAdvanced Graphs
← Back to All Problems

#651 · #3203 · Find Minimum Diameter After Merging Two Trees(合并两棵树后的最小直径)

📌 Problem Statement & Constraints

You are given two trees described by edges1 and edges2. You must add exactly one edge connecting a node of the first tree to a node of the second. Return the minimum possible diameter of the resulting tree. Constraints: 1 <= number of nodes <= 10^5.

💡 Core Algorithmic Approaches

  1. The diameter of the merged tree is the maximum of three quantities:
  2. ① the first tree's own diameter; ② the second tree's own diameter; ③ radius1 + radius2 + 1 (the new edge plus the best attachment points).
  3. The best attachment points are the centres, so the radius is ceil(diameter / 2).
  4. A tree's diameter is found with two BFS passes (the classic "farthest from any node, then farthest from that" trick).

💻 Benchmark Python3 Implementation

class Solution:
    def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
        from collections import defaultdict, deque

        def diameter_and_radius(edges):
            g = defaultdict(list)
            for a, b in edges:
                g[a].append(b)
                g[b].append(a)
            if not g:
                return 0, 0                # a single node

            def bfs(start):
                dist = {start: 0}
                q = deque([start])
                far = start
                while q:
                    node = q.popleft()
                    for nxt in g[node]:
                        if nxt not in dist:
                            dist[nxt] = dist[node] + 1
                            q.append(nxt)
                            if dist[nxt] > dist[far]:
                                far = nxt
                return far, dist[far]

            a, _ = bfs(0)                  # farthest from an arbitrary node
            b, d = bfs(a)                  # farthest from a -> the diameter
            return d, (d + 1) // 2         # diameter, and the radius (ceil(d/2))

        d1, r1 = diameter_and_radius(edges1)
        d2, r2 = diameter_and_radius(edges2)
        return max(d1, d2, r1 + r2 + 1)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + m): two BFS passes per tree.
💾 Space Complexity
O(n + m) for the adjacency lists.

⚠️ Interview Pitfalls & Follow-ups

  • Attaching at arbitrary nodes: the centres minimise the resulting radius.
  • Using d // 2 for the radius: the ceiling is required, hence (d + 1) // 2.
  • Forgetting to include both original diameters: the merged diameter is at least each of them.
  • Handling a single-node tree: the diameter is 0 and the radius is 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems