Find Minimum Diameter After Merging Two Trees
HardPrompt
There exist two undirected trees with n and m nodes, numbered from 0 to n - 1 and from 0 to m - 1, respectively. You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the first tree and edges2[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the second tree.
You must connect one node from the first tree with another node from the second tree with an edge.
Return the minimum possible diameter of the resulting tree.
The diameter of a tree is the length of the longest path between any two nodes in the tree.
Example 1:
Input: edges1 = [[0,1],[0,2],[0,3]], edges2 = [[0,1]]
Output: 3
Explanation:
We can obtain a tree of diameter 3 by connecting node 0 from the first tree with any node from the second tree.
Example 2:
Input: edges1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]], edges2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]
Output: 5
Explanation:
We can obtain a tree of diameter 5 by connecting node 0 from the first tree with node 0 from the second tree.
Constraints:
1 <= n, m <= 105edges1.length == n - 1edges2.length == m - 1edges1[i].length == edges2[i].length == 2edges1[i] = [ai, bi]0 <= ai, bi < nedges2[i] = [ui, vi]0 <= ui, vi < m- The input is generated such that
edges1andedges2represent valid trees.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves finding the diameter of each tree by computing the distance between every pair of nodes and selecting the maximum distance. This is a straightforward but computationally expensive method. After finding the diameters of both trees, diam1 and diam2, the minimum diameter of the merged tree is calculated. The new diameter can either be diam1, diam2, or the length of the longest path that crosses the new connecting edge. To minimize the length of this crossing path, we connect the centers of the two trees. The length of this path is radius1 + 1 + radius2, where radius is the minimum eccentricity of a node in a tree. The final result is max(diam1, diam2, radius1 + 1 + radius2).
Algorithm
- Build Adjacency Lists: For each tree, create an adjacency list from the given edges to represent the tree structure.
- Calculate Diameter (Brute-Force):
- For each tree, implement a function
getDiameterBruteForce. - Inside this function, iterate through every node
uin the tree. - For each node
u, run a Breadth-First Search (BFS) starting fromuto find the maximum distance to any other nodev. - The diameter of the tree is the maximum of these distances found over all possible starting nodes
u.
- For each tree, implement a function
- Find Diameters of Both Trees: Call the brute-force diameter function for both
tree1andtree2to getdiam1anddiam2. - Calculate Radii: The radius of a tree can be calculated from its diameter using the formula
radius = ceil(diameter / 2), which is equivalent to(diameter + 1) / 2with integer arithmetic. - Compute Final Result: The minimum possible diameter of the merged tree is
max(diam1, diam2, radius1 + 1 + radius2). Return this value.
Walkthrough
The core of this method is a brute-force calculation of each tree's diameter. For a tree with n nodes, we perform a BFS/DFS from each of the n nodes to find the farthest node from it. The maximum of these n maximum distances gives the diameter. While correct, this is slow. Once both diameters are found, we use the formula to find the minimum merged diameter.
import java.util.*; class Solution { // Helper function to run BFS from a start node and find the max distance private int bfsForMaxDistance(int startNode, int numNodes, List<List<Integer>> adj) { int[] dist = new int[numNodes]; Arrays.fill(dist, -1); Queue<Integer> q = new LinkedList<>(); q.offer(startNode); dist[startNode] = 0; int maxDist = 0; while (!q.isEmpty()) { int u = q.poll(); maxDist = Math.max(maxDist, dist[u]); for (int v : adj.get(u)) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.offer(v); } } } return maxDist; } // Function to calculate diameter using brute-force private int getDiameterBruteForce(int numNodes, List<List<Integer>> adj) { if (numNodes <= 1) return 0; int diameter = 0; for (int i = 0; i < numNodes; i++) { diameter = Math.max(diameter, bfsForMaxDistance(i, numNodes, adj)); } return diameter; } public int minDiameterAfterMerge(int[][] edges1, int[][] edges2) { int n = edges1.length + 1; List<List<Integer>> adj1 = new ArrayList<>(); for (int i = 0; i < n; i++) adj1.add(new ArrayList<>()); for (int[] edge : edges1) { adj1.get(edge[0]).add(edge[1]); adj1.get(edge[1]).add(edge[0]); } int m = edges2.length + 1; List<List<Integer>> adj2 = new ArrayList<>(); for (int i = 0; i < m; i++) adj2.add(new ArrayList<>()); for (int[] edge : edges2) { adj2.get(edge[0]).add(edge[1]); adj2.get(edge[1]).add(edge[0]); } int diam1 = getDiameterBruteForce(n, adj1); int diam2 = getDiameterBruteForce(m, adj2); int radius1 = (diam1 + 1) / 2; int radius2 = (diam2 + 1) / 2; return Math.max(diam1, Math.max(diam2, radius1 + radius2 + 1)); }}Complexity
Time
O(n^2 + m^2), where `n` and `m` are the number of nodes in the first and second trees, respectively. For each tree, we run a BFS/DFS from every node. A single BFS/DFS takes O(V+E) time, which is O(n) for a tree. Repeating this for all `n` nodes results in O(n^2) time. Thus, the total time is dominated by the two diameter calculations.
Space
O(n + m). The space is primarily used for storing the adjacency lists for both trees and the auxiliary data structures for BFS/DFS (queue, distance array), which require O(n) and O(m) space respectively.
Trade-offs
Pros
Conceptually simple and easy to implement.
The logic for calculating the final merged diameter is sound.
Cons
Highly inefficient due to the O(n^2) complexity for diameter calculation.
Will likely cause a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
This optimal approach calculates the tree diameter in linear time using a well-known two-pass algorithm. First, run a BFS/DFS from an arbitrary node s to find the farthest node u. Then, run a second BFS/DFS from u to find the farthest node v. The distance between u and v is the diameter of the tree. This efficient method is applied to both trees to find diam1 and diam2. The final minimum merged diameter is then computed using the same formula as in the brute-force approach: max(diam1, diam2, radius1 + 1 + radius2).
Algorithm
- Define Diameter Helper Function: Create a helper function, e.g.,
getDiameterEfficient, that takes the number of nodes and edges of a tree and returns its diameter. - Inside the Helper Function:
- Build the adjacency list for the tree.
- First BFS: Run a BFS starting from an arbitrary node (e.g., node 0). The purpose of this BFS is to find one of the endpoints of a longest path. The last node visited in the BFS is guaranteed to be one such endpoint.
- Second BFS: Run another BFS starting from the endpoint found in the previous step. The maximum distance found during this second BFS is the diameter of the tree.
- Find Diameters of Both Trees: Call this efficient helper function for both
tree1andtree2to obtaindiam1anddiam2. - Calculate Radii: Compute the radii for both trees:
radius1 = (diam1 + 1) / 2andradius2 = (diam2 + 1) / 2. - Compute Final Result: The minimum diameter of the merged tree is
max(diam1, diam2, radius1 + 1 + radius2). Return this value.
Walkthrough
The key to this approach is an efficient O(n) algorithm for finding a tree's diameter. It works in two steps:
- Start a BFS from any node
sand find the nodeuthat is farthest froms. - Start a second BFS from
u. The farthest nodevfound fromuwill form a diameter pathu-...-v. The length of this path is the diameter.
We apply this efficient algorithm to both trees and then use the same logic as the previous approach to find the minimum merged diameter.
import java.util.*; class Solution { // Helper BFS function that returns {farthestNode, farthestDistance} private int[] bfs(int startNode, int numNodes, List<List<Integer>> adj) { int[] dist = new int[numNodes]; Arrays.fill(dist, -1); Queue<Integer> q = new LinkedList<>(); q.offer(startNode); dist[startNode] = 0; int farthestNode = startNode; while (!q.isEmpty()) { int u = q.poll(); farthestNode = u; // The last node dequeued will be one of the farthest for (int v : adj.get(u)) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.offer(v); } } } return new int[]{farthestNode, dist[farthestNode]}; } // Function to calculate diameter efficiently using two BFS passes private int getDiameterEfficient(int numNodes, int[][] edges) { if (numNodes <= 1) { return 0; } List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numNodes; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } // 1st BFS to find one endpoint of a diameter int[] result1 = bfs(0, numNodes, adj); int farthestNodeFromStart = result1[0]; // 2nd BFS from that endpoint to find the diameter int[] result2 = bfs(farthestNodeFromStart, numNodes, adj); return result2[1]; // The diameter } public int minDiameterAfterMerge(int[][] edges1, int[][] edges2) { int n = edges1.length + 1; int m = edges2.length + 1; int diam1 = getDiameterEfficient(n, edges1); int diam2 = getDiameterEfficient(m, edges2); int radius1 = (diam1 + 1) / 2; int radius2 = (diam2 + 1) / 2; return Math.max(diam1, Math.max(diam2, radius1 + radius2 + 1)); }}Complexity
Time
O(n + m). Each diameter calculation involves two BFS runs on a tree. A single BFS takes O(V+E) time, which is O(n) or O(m) for a tree. Therefore, finding both diameters takes O(n) + O(m) time. The rest of the operations are constant time. The overall complexity is linear.
Space
O(n + m). Space is required for the adjacency lists (O(n+m)) and the data structures used by BFS (queue, distance array), which take O(n) and O(m) space for each tree respectively.
Trade-offs
Pros
Optimal time complexity, making it very efficient for large inputs.
Correctly solves the problem within typical time limits.
Cons
The proof of correctness for the two-BFS diameter algorithm is slightly more involved than the brute-force method, making it less immediately obvious.
Solutions
Solution
class Solution {private List<Integer>[] g;private int ans;private int a;public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) { int d1 = treeDiameter(edges1); int d2 = treeDiameter(edges2); return Math.max(Math.max(d1, d2), (d1 + 1) / 2 + (d2 + 1) / 2 + 1); }public int treeDiameter(int[][] edges) { int n = edges.length + 1; g = new List[n]; Arrays.setAll(g, k->new ArrayList<>()); ans = 0; a = 0; for (var e : edges) { int a = e[0], b = e[1]; g[a].add(b); g[b].add(a); } dfs(0, -1, 0); dfs(a, -1, 0); return ans; }private void dfs(int i, int fa, int t) { for (int j : g[i]) { if (j != fa) { dfs(j, i, t + 1); } } if (ans < t) { ans = t; a = i; } }}class Solution {public: int minimumDiameterAfterMerge(vector<vector<int>> &edges1, vector<vector<int>> &edges2) { int d1 = treeDiameter(edges1); int d2 = treeDiameter(edges2); return max({d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2 + 1}); } int treeDiameter(vector<vector<int>> &edges) { int n = edges.size() + 1; vector<int> g[n]; for (auto &e : edges) { int a = e[0], b = e[1]; g[a].push_back(b); g[b].push_back(a); } int ans = 0, a = 0; auto dfs = [&](auto &&dfs, int i, int fa, int t) -> void { for (int j : g[i]) { if (j != fa) { dfs(dfs, j, i, t + 1); } } if (ans < t) { ans = t; a = i; } }; dfs(dfs, 0, -1, 0); dfs(dfs, a, -1, 0); return ans; }};class Solution: def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int: d1 = self . treeDiameter(edges1) d2 = self . treeDiameter(edges2) return max(d1, d2, (d1 + 1) // 2 + (d2 + 1) // 2 + 1) def treeDiameter(self, edges: List[List[int]]) -> int: def dfs(i: int, fa: int, t: int): for j in g[i]: if j != fa: dfs(j, i, t + 1) nonlocal ans, a if ans < t: ans = t a = i g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) ans = a = 0 dfs(0, - 1, 0) dfs(a, - 1, 0) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.