# Find Minimum Diameter After Merging Two Trees
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-minimum-diameter-after-merging-two-trees)
Canonical: https://scaleengineer.com/dsa/problems/find-minimum-diameter-after-merging-two-trees
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Graph
**Companies:** [ServiceNow](https://scaleengineer.com/companies/servicenow)
---
## Problem
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:**![](https://assets.glich.co/dsa/find-minimum-diameter-after-merging-two-trees/image0.png)

**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:**

![](https://assets.glich.co/dsa/find-minimum-diameter-after-merging-two-trees/image1.png) 

**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 <= 105`
* `edges1.length == n - 1`
* `edges2.length == m - 1`
* `edges1[i].length == edges2[i].length == 2`
* `edges1[i] = [ai, bi]`
* `0 <= ai, bi < n`
* `edges2[i] = [ui, vi]`
* `0 <= ui, vi < m`
* The input is generated such that `edges1` and `edges2` represent valid trees.

# Approaches
## Brute-Force Diameter Calculation
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)`.
**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.
**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.
### Explanation
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.

```java
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));
    }
}
```
### 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 `u` in the tree.
    *   For each node `u`, run a Breadth-First Search (BFS) starting from `u` to find the maximum distance to any other node `v`.
    *   The diameter of the tree is the maximum of these distances found over all possible starting nodes `u`.
*   **Find Diameters of Both Trees:** Call the brute-force diameter function for both `tree1` and `tree2` to get `diam1` and `diam2`.
*   **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) / 2` with integer arithmetic.
*   **Compute Final Result:** The minimum possible diameter of the merged tree is `max(diam1, diam2, radius1 + 1 + radius2)`. Return this value.

## Efficient Diameter Calculation with Two-BFS
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)`.
**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.
**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.
### Explanation
The key to this approach is an efficient O(n) algorithm for finding a tree's diameter. It works in two steps:
1.  Start a BFS from any node `s` and find the node `u` that is farthest from `s`.
2.  Start a second BFS from `u`. The farthest node `v` found from `u` will form a diameter path `u-...-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.

```java
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));
    }
}
```
### 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 `tree1` and `tree2` to obtain `diam1` and `diam2`.
*   **Calculate Radii:** Compute the radii for both trees: `radius1 = (diam1 + 1) / 2` and `radius2 = (diam2 + 1) / 2`.
*   **Compute Final Result:** The minimum diameter of the merged tree is `max(diam1, diam2, radius1 + 1 + radius2)`. Return this value.

# Solutions
### Java

```java
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;
    }
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```