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.

Examples

Example 1:

graph TD
    subgraph Tree_1
        0 --- 1
        0 --- 2
        0 --- 3
    end

    subgraph Tree_2
        A[0] --- B[1]
    end

    0 -.- A
  
1
2
3

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:

graph TD
    subgraph Tree_1
        0 --- 1
        0 --- 2
        0 --- 3
        2 --- 4
        2 --- 5
        3 --- 6
        2 --- 7
    end

    subgraph Tree_2
        A[0] --- B[1]
        A --- C[2]
        A --- D[3]
        C --- E[4]
        C --- F[5]
        D --- G[6]
        C --- H[7]
    end

    0 -.- A
  
1
2
3

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.

Solution

Method 1 - BFS

To solve this problem, we need to connect one node from the first tree with another node from the second tree in such a way that the resulting tree has the minimum possible diameter. Here’s a structured approach to solving this:

Approach

  1. Understanding Diameter: The diameter of a tree is the length of the longest path between any two nodes. For a given tree, this can be determined using a two-pass BFS or DFS.
  2. Combining Two Trees:
    • Compute the diameter (D1) of the first tree.
    • Compute the diameter (D2) of the second tree.
    • When we add an edge between any node in the first tree and any node in the second tree, the resulting diameter will at most be the maximum of:
      • The sum of D1 and D2 divided by 2 ((D1 + 1) / 2 + (D2 + 1) / 2 + 1).
  3. Choosing Optimal Connection:
    • There’s no need to test all node pairs. The worst-case scenario would be adding one node at the diameter path in one tree to a node at the diameter path in the other tree.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

public class Solution {
    
    public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
        int n = edges1.length + 1; // Number of nodes in first tree
        int m = edges2.length + 1; // Number of nodes in second tree

        Tree tree1 = new Tree(edges1, n);
        Tree tree2 = new Tree(edges2, m);

        int d1 = tree1.diameter;
        int d2 = tree2.diameter;

        int ans = Math.max(d1, d2);
        ans = Math.max(ans, (d1 + 1) / 2 + (d2 + 1) / 2 + 1);

        return ans;
    }

    private class Tree {
        int diameter;
        int[] depth;

        public Tree(int[][] edges, int n) {
            diameter = 0;
            depth = new int[n];

            List<Integer>[] graph = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
            }
            for (int[] edge : edges) {
                graph[edge[0]].add(edge[1]);
                graph[edge[1]].add(edge[0]);
            }

            int farthest = bfs(0, graph, n); // first endpoint
            int other = bfs(farthest, graph, n); // second endpoint

            diameter = depth[other];
        }

        private int bfs(int start, List<Integer>[] graph, int n) {
            Arrays.fill(depth, 0);
            Queue<Integer> q = new LinkedList<>();
            q.add(start);
            boolean[] visited = new boolean[n];
            visited[start] = true;

            int node = start;
            while (!q.isEmpty()) {
                node = q.poll();
                for (int neighbor : graph[node]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        depth[neighbor] = depth[node] + 1;
                        q.add(neighbor);
                    }
                }
            }
            return node;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution:
    def minimum_diameter_after_merge(self, edges1: List[Tuple[int, int]], edges2: List[Tuple[int, int]]) -> int:
        n = len(edges1) + 1
        m = len(edges2) + 1
        
        tree1 = self.Tree(edges1, n)
        tree2 = self.Tree(edges2, m)
        
        d1 = tree1.diameter
        d2 = tree2.diameter
        
        ans = max(d1, d2)
        ans = max(ans, (d1 + 1) // 2 + (d2 + 1) // 2 + 1)
        
        return ans
    
    class Tree:
        def __init__(self, edges: List[Tuple[int, int]], n: int):
            self.diameter = 0
            self.depth = [0] * n

            graph = [[] for _ in range(n)]
            for u, v in edges:
                graph[u].append(v)
                graph[v].append(u)
            
            def bfs(start: int) -> int:
                self.depth = [0] * n
                q = deque([start])
                visited = [False] * n
                visited[start] = True
                
                node = start
                while q:
                    node = q.popleft()
                    for neighbor in graph[node]:
                        if not visited[neighbor]:
                            visited[neighbor] = True
                            self.depth[neighbor] = self.depth[node] + 1
                            q.append(neighbor)
                return node
            
            first_end = bfs(0)
            second_end = bfs(first_end)
            self.diameter = self.depth[second_end]

Complexity

  • ⏰ Time complexity: O(n + m) for traversing both trees.
    • We use two-pass BFS to determine the diameter of an undirected tree. This is done by finding the furthest node from a given starting node and then finding the furthest node from that node.
    • Connect the trees in the way that minimally increases the diameter.
    • The longest possible new diameter would be considering the two initial diameters.
  • 🧺 Space complexity: O(n + m) for storing graphs and BFS queues.