Practice/Microsoft/Leetcode 3203. Find Minimum Diameter After Merging Two Trees

Leetcode 3203. Find Minimum Diameter After Merging Two Trees

CodingOptional

Problem

You are given two undirected trees represented as edge lists. Each tree is connected and acyclic. Your task is to add exactly one edge between a node from the first tree and a node from the second tree, creating a single larger tree.

Your goal is to choose which two nodes to connect such that the diameter of the resulting merged tree is minimized. Return this minimum possible diameter.

The diameter of a tree is defined as the length of the longest path between any two nodes in the tree, measured by the number of edges.

Requirements

1. Build adjacency lists for both trees from their edge lists
2. Calculate the diameter of each tree independently
3. Determine the optimal connection strategy that minimizes the merged tree's diameter
4. Return the minimum achievable diameter as an integer

Constraints

• 1 ≤ number of nodes in each tree ≤ 100,000
• edges1.length == n1 - 1 (where n1 is the number of nodes in tree 1)
• edges2.length == n2 - 1 (where n2 is the number of nodes in tree 2)
• All edges are valid and form connected trees
• Node indices start from 0
• Time complexity should be O(n1 + n2)
• Space complexity should be O(n1 + n2)

Examples

Example 1:

Input: edges1 = [[0,1],[0,2]], edges2 = [[0,1]] Output: 3 Explanation: Tree 1 has nodes \{0,1,2\} with diameter 2 (path from node 1 to node 2 through 0). Tree 2 has nodes \{0,1\} with diameter 1. When we connect optimally, the minimum diameter is 3.

Example 2:

Input: edges1 = [[0,1],[1,2],[2,3]], edges2 = [[0,1],[1,2]] Output: 4 Explanation: Tree 1 is a linear chain with diameter 3. Tree 2 is a linear chain with diameter 2. Connecting the middle nodes of each chain gives us a minimum diameter of 4.

Example 3:

Input: edges1 = [], edges2 = [] Output: 1 Explanation: Both trees consist of a single node. Adding one edge creates a tree with diameter 1.