Solution: Find Minimum Diameter After Merging Two Trees

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$

• edges2.length $== m - 1$

• edges1[i].length $==$ edges2[i].length $== 2$

• edges1[i] = [ai, bi]

• $0 <= a_i, b_i < n$

• edges2[i] = [ui, vi]

• $0 <= u_i, v_i < m$

• The input is generated such that edges1 and edges2 represent valid trees.

Solution

To solve this problem, we use the tree breadth-first search (BFS) pattern. The intuition behind this pattern lies in the fact that breadth-first search naturally discovers the shortest paths level by level, making it ideal for finding the farthest nodes in a tree. We can accurately and efficiently find a tree’s diameter by doing two passes of breadth-first search.

Here’s how two passes of breadth-first search work:

1. Farthest node from any node: If we start at an arbitrary node and perform a breadth-first search in any tree, we will eventually reach the farthest node from the start. Let’s call this node $A$.

2. Second farthest node: From node $A$, perform another breadth-first search. The farthest node found in this second breadth-first search will be the other end of the diameter. The distance between these two nodes is the diameter of the tree.

Once we know the diameters of both trees individually, we don’t need to test every node pairing. Instead, we can rely on a mathematical insight.

The worst-case diameter when connecting two trees is bounded by