#3203

Hard

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Find Minimum Diameter After Merging Two Trees

Calculate the minimum diameter after merging two trees by strategically connecting nodes to minimize the longest path in the combined graph.

tree depth first search breadth first search graph

Problem Statement

You are given two undirected trees represented as edge lists edges1 and edges2, containing n - 1 and m - 1 edges, respectively. Nodes are labeled from 0 to n - 1 in the first tree and from 0 to m - 1 in the second tree. Each edge connects two nodes within its own tree.

Your task is to connect exactly one node from the first tree with one node from the second tree, creating a single combined tree. Return the minimum possible diameter of this new tree, which is defined as the length of the longest path between any two nodes after the connection.

Examples

Example 1

Input: edges1 = [[0,1],[0,2],[0,3]], edges2 = [[0,1]]

Output: 3

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

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 Approach

Compute individual tree diameters

Use BFS or DFS to find the diameter of each tree separately. Start from any node and find the farthest node to determine one end of the diameter, then repeat from that node to get the maximum distance. This step ensures you know the largest internal paths before merging.

Determine optimal connecting nodes

Consider nodes near the diameters' endpoints for connection. Connecting deep nodes reduces the longest path increase. Use the formula max((diam1 + 1 + diam2 + 1)/2, diam1, diam2) to estimate the minimum possible diameter after merging.

Calculate resulting diameter

After choosing candidate nodes, compute the resulting diameter by checking the longest path through the connection. This ensures the final diameter accounts for both original diameters and the connecting edge, giving the minimum achievable length.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(n + m)

Time complexity is O(n + m) because BFS or DFS traverses each node once in both trees. Space complexity is O(n + m) to store adjacency lists for each tree and recursive or queue storage during traversal.

What Interviewers Usually Probe

Expect candidates to quickly identify diameter endpoints using BFS or DFS.
Watch for reasoning on how connecting nodes affects the combined tree's diameter.
Notice whether candidates correctly optimize the maximum path rather than connecting arbitrarily.

Common Pitfalls or Variants

Common pitfalls

Choosing arbitrary nodes instead of endpoints can lead to non-minimal diameters.
Neglecting the internal diameter of each tree before merging can miscalculate the final result.
Forgetting to consider the longest path that passes through the connecting edge may produce incorrect outputs.

Follow-up variants

Compute minimum diameter when merging more than two trees sequentially.
Find the maximum diameter instead of minimum after connecting trees.
Apply the same logic to weighted trees where edges have lengths other than 1.

FAQ

How do I choose which nodes to connect in Find Minimum Diameter After Merging Two Trees?

Pick nodes near the endpoints of each tree's diameter; connecting shallow nodes rarely reduces the maximum path length.

Can this method handle large trees efficiently?

Yes, using BFS or DFS ensures O(n + m) time complexity, which scales linearly with the number of nodes.

Why is it necessary to compute each tree's diameter first?

Knowing each tree's diameter helps determine the minimum possible combined diameter and identifies optimal nodes to connect.

Does the connecting edge always increase the diameter by one?

Not necessarily; the increase depends on which nodes are connected and how the diameters of the original trees interact.

Is BFS better than DFS for this problem?

Either works for finding farthest nodes; BFS may be easier to implement iteratively, while DFS can use recursion.

terminal

Solution

Solution 1: Two DFS Passes

We denote $d_1$ and $d_2$ as the diameters of the two trees, respectively. Then, the diameter of the merged tree can be one of the following two cases:

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

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

Continue Practicing

#2477 minimum fuel cost to report to the capital #2467 most profitable path in a tree #2368 reachable nodes with restrictions