Solution: Find Minimum Diameter After Merging Two Trees

Explore how to use breadth-first search to find the minimum possible diameter when merging two undirected trees. Understand how to compute each tree's diameter with BFS and apply a formula to connect trees optimally, minimizing the resulting diameter. This lesson helps you develop efficient algorithms with time and space complexity analysis for large trees.

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$ ...