Solution: Find Minimum Diameter After Merging Two Trees

Explore how to compute the smallest diameter after connecting two undirected trees using breadth-first search. Understand the BFS approach to find tree diameters and apply a formula to minimize the combined tree's longest path efficiently. This lesson guides you through adjacency list construction, BFS traversals, and diameter calculation with clear complexity analysis.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given two undirected trees: one with $n$ nodes labeled from $0$ to $n - 1$ , and another with $m$ nodes labeled from $0$ to $m - 1$ . Their structures are defined by two $2D$ integer arrays—edges1 of length $n - 1$ for the first tree, and edges2 of length $m - 1$ for the second. Each element edges1[i] = [aᵢ, bᵢ] represents an edge between nodes $aᵢ$ and $bᵢ$ in the first tree, and similarly, edges2[i] = [uᵢ, vᵢ] represents an edge in the second tree.

Your task is to connect any node from the first tree to any one node from the second tree using a single edge. Return the smallest possible diameter of the resulting combined tree.

Note: The diameter of a tree is the length of the longest path between any two nodes in it.

Constraints:

$1 <= n, m <= 10^5$
edges1.length $== n - 1$ ...