Solution: Find Minimum Diameter After Merging Two Trees

Explore how to compute the minimum possible diameter after connecting two trees by leveraging breadth-first search techniques. Understand how to find each tree's diameter and apply the formula to determine the smallest combined diameter. This lesson guides you through efficient BFS traversal, adjacency list construction, and the conceptual approach to minimize the diameter after merging 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$ ...