3203. Find Minimum Diameter After Merging Two Trees - Detailed Explanation

Problem Statement

You are given two trees, Tree1 and Tree2.
Each tree is provided as an edge list with a given number of nodes (nodes are labeled from 1 to n).
You are allowed to merge these two trees by adding one edge between any node in Tree1 and any node in Tree2.
After merging, the tree’s diameter is defined as the length of the longest shortest path between any two nodes in the merged tree.
Your task is to determine the minimum possible diameter that can be achieved by optimally choosing the two nodes to connect.

Example 1

Let Tree1 be a path of 4 nodes:

• Nodes: 1, 2, 3, 4
• Edges: (1,2), (2,3), (3,4)
• Diameter of Tree1: 3
• Radius of Tree1: ⎡3⁄2⎤ = 2

Let Tree2 also be a path of 4 nodes:

• Nodes: 1, 2, 3, 4
• Edges: (1,2), (2,3), (3,4)
• Diameter of Tree2: 3
• Radius of Tree2: 2

If you connect the “centers” of the two trees (i.e. nodes that are approximately in the middle), then the merged tree will have a diameter given by:
max( diameter(Tree1), diameter(Tree2), radius(Tree1) + radius(Tree2) + 1 )
In this case:
max(3, 3, 2 + 2 + 1) = max(3, 3, 5) = 5.
Thus, the minimum achievable diameter after merging is 5.

Example 2

Let Tree1 be a star with 4 nodes:

• Edges: (1,2), (1,3), (1,4)
• Diameter of Tree1: 2 (any two leaves are connected via the center)
• Radius of Tree1: ⎡2⁄2⎤ = 1

Let Tree2 be another star with 4 nodes:

• Edges: (1,2), (1,3), (1,4)
• Diameter of Tree2: 2
• Radius of Tree2: 1

Then the merged tree’s diameter is:
max(2, 2, 1 + 1 + 1) = max(2, 2, 3) = 3.
So the answer is 3.

Constraints

• Each tree is acyclic and connected.
• 1 ≤ number of nodes in each tree ≤ 10⁵
• The trees are given as lists of edges.

Hints

1. Diameter and Radius of a Tree:

   • The diameter is the longest distance between any two nodes.
   • The radius is the minimum “eccentricity” among all nodes (i.e. the minimum distance from a node to the furthest node in the tree). For any tree, it can be shown that
     [ \text{radius} = \lceil \frac{\text{diameter}}{2} \rceil. ]

2. Optimal Merge Insight:

   • When merging two trees by adding one edge, you can “bridge” their diameters. The best you can do is connect near the centers of each tree.
   • The resulting diameter is the maximum of:
     • The original diameter of Tree1.
     • The original diameter of Tree2.
     • The sum of the radii of Tree1 and Tree2 plus 1 (for the connecting edge).
   • Therefore, the minimum possible diameter after merging is:
     [ \text{Answer} = \max\Big( \text{diameter(Tree1)},\, \text{diameter(Tree2)},\, \text{radius(Tree1)} + \text{radius(Tree2)} + 1 \Big). ]

3. Computing the Diameter:

   • One standard method is to perform a two-phase DFS/BFS:
     1. Pick an arbitrary node and find the farthest node (u).
     2. From (u), perform another DFS/BFS to find the farthest node (v). The distance from (u) to (v) is the diameter.

Approach 1: Compute Diameters and Radii, Then Use the Merging Formula

Steps

1. For Each Tree:

   • Use two DFS/BFS traversals to compute the diameter.
   • Compute the radius as:
     [ \text{radius} = \lceil \frac{\text{diameter}}{2} \rceil \quad \text{(which can be computed as } ( \text{diameter} + 1 ) // 2 \text{ in integer math)} ]

2. Combine the Results:

   • Let (d_1) and (d_2) be the diameters of Tree1 and Tree2, and (r_1) and (r_2) be their radii.
   • The minimum possible diameter after merging is:
     [ \text{result} = \max( d_1,\, d_2,\, r_1 + r_2 + 1 ). ]

Why It Works

• If you connect the two trees near their centers, the extra “bridge” needed is as short as possible.
• The merged diameter must be at least as long as the diameter of either tree.
• In the “bridge” case, the new diameter can be no less than the sum of the two radii plus the connecting edge.
• Taking the maximum of these three quantities yields the minimum possible diameter over all valid merges.

Code Solutions

Python Code