Find Minimum Diameter After Merging Two Trees

Find Minimum Diameter After Merging Two Trees

What is this problem about?

The Find Minimum Diameter After Merging Two Trees interview question is a high-level graph theory problem. You are given two separate trees and you must add exactly one edge to connect them into a single tree. Your objective is to choose the connection points such that the "diameter" (the longest path between any two nodes) of the resulting merged tree is as small as possible.

Why is this asked in interviews?

Companies like Google and ServiceNow use the Find Minimum Diameter After Merging Two Trees coding problem to test a candidate's mastery of tree properties. It requires understanding tree centers, radii, and diameters. It evaluates whether you can combine multiple Tree interview patterns—such as finding the longest path and the "midpoint" of a tree—to solve a global optimization task.

Algorithmic pattern used

This problem relies on Breadth-First Search (BFS) or Depth-First Search (DFS) to find tree diameters and centers.

1. Find Diameters: Independently calculate the diameter ($D_1, D_2$) of both trees.
2. Find Radii: The "radius" of a tree is the distance from its center to the farthest node. To minimize the new diameter, you must connect the trees at their respective centers. The radius $R$ is approximately $ceil(D/2)$.
3. Merge Calculation: The new diameter will be the maximum of three values:
   • The diameter of the first tree ($D_1$).
   • The diameter of the second tree ($D_2$).
   • The path created by the new edge: $R_1 + R_2 + 1$.

Example explanation

Tree 1 has a diameter of 4 (Radius 2). Tree 2 has a diameter of 2 (Radius 1).

• If we connect the centers, the new path through the edge is $2 + 1 + 1 = 4$.
• The merged tree diameter is $max(4, 2, 4) = 4$. Connecting at any other nodes would increase the $R_1 + R_2 + 1$ component, making the diameter larger.

Common mistakes candidates make

• Connecting Leaves: Intuitively thinking that connecting leaves is best, while connecting centers is actually the optimal strategy.
• Off-by-one: Miscalculating the relationship between diameter and radius ($R = (D+1)/2$ using integer division).
• Complexity: Running BFS from every single node to find the center, instead of using the two-BFS method to find the diameter in $O(V+E)$.

Interview preparation tip

Master the "Two BFS" technique for tree diameters: BFS from an arbitrary node to find the farthest node $A$, then BFS from $A$ to find the farthest node $B$. The distance $A-B$ is the diameter. This is a core Graph interview pattern for tree-based metrics.