Find Minimum Diameter After Merging Two Trees

Problem#

You are given two trees with edge lists edges1 and edges2. You must add exactly one edge between any node of tree 1 and any node of tree 2, forming a single tree. Return the minimum possible diameter of the merged tree.

Examples#

edges1 = [[0,1],[0,2],[0,3]], edges2 = [[0,1]] → 3.
Two paths of length 4 each → connect midpoints, merged diameter = max(d1, d2, ceil(d1/2)+ceil(d2/2)+1).

Constraints#

1 <= n, m <= 10^5. Each input is a valid tree.

Hints#

Hint 1

Connecting two trees optimally means joining their centroid-like middles.

Hint 2

Best new diameter = max(d1, d2, ceil(d1/2) + ceil(d2/2) + 1).

Approach#

Compute each tree’s diameter d1, d2 independently via two BFS sweeps (farthest-from-any, then farthest-from-that). The merged diameter is max(d1, d2, ceil(d1/2) + ceil(d2/2) + 1) — connecting the trees at their radii midpoints.

Solution#

class Solution {
public:
    int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        int d1 = treeDiameter(edges1);
        int d2 = treeDiameter(edges2);
        int combined = (d1 + 1) / 2 + (d2 + 1) / 2 + 1;
        return max({d1, d2, combined});
    }
private:
    int treeDiameter(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        if (n == 1) return 0;
        vector<vector<int>> g(n);
        for (auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
        auto bfsFarthest = [&](int src) -> pair<int,int> {
            vector<int> dist(n, -1);
            queue<int> q;
            q.push(src); dist[src] = 0;
            int far = src;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                if (dist[u] > dist[far]) far = u;
                for (int v : g[u]) if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
            return {far, dist[far]};
        };
        auto [a, _] = bfsFarthest(0);
        auto [b, d] = bfsFarthest(a);
        return d;
    }
};

func treeDiameter(edges [][]int) int {
    n := len(edges) + 1
    if n == 1 {
        return 0
    }
    g := make([][]int, n)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
        g[e[1]] = append(g[e[1]], e[0])
    }
    bfsFarthest := func(src int) (int, int) {
        dist := make([]int, n)
        for i := range dist {
            dist[i] = -1
        }
        q := []int{src}
        dist[src] = 0
        far := src
        for len(q) > 0 {
            u := q[0]
            q = q[1:]
            if dist[u] > dist[far] {
                far = u
            }
            for _, v := range g[u] {
                if dist[v] == -1 {
                    dist[v] = dist[u] + 1
                    q = append(q, v)
                }
            }
        }
        return far, dist[far]
    }
    a, _ := bfsFarthest(0)
    _, d := bfsFarthest(a)
    return d
}

func minimumDiameterAfterMerge(edges1 [][]int, edges2 [][]int) int {
    d1 := treeDiameter(edges1)
    d2 := treeDiameter(edges2)
    combined := (d1+1)/2 + (d2+1)/2 + 1
    ans := d1
    if d2 > ans {
        ans = d2
    }
    if combined > ans {
        ans = combined
    }
    return ans
}

from typing import List
from collections import deque

class Solution:
    def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
        d1 = self._treeDiameter(edges1)
        d2 = self._treeDiameter(edges2)
        combined = (d1 + 1) // 2 + (d2 + 1) // 2 + 1
        return max(d1, d2, combined)

    def _treeDiameter(self, edges: List[List[int]]) -> int:
        n = len(edges) + 1
        if n == 1:
            return 0
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

        def bfs_farthest(src: int):
            dist = [-1] * n
            dist[src] = 0
            q = deque([src])
            far = src
            while q:
                u = q.popleft()
                if dist[u] > dist[far]:
                    far = u
                for v in g[u]:
                    if dist[v] == -1:
                        dist[v] = dist[u] + 1
                        q.append(v)
            return far, dist[far]

        a, _ = bfs_farthest(0)
        _, d = bfs_farthest(a)
        return d

function minimumDiameterAfterMerge(edges1, edges2) {
    const treeDiameter = (edges) => {
        const n = edges.length + 1;
        if (n === 1) return 0;
        const g = Array.from({ length: n }, () => []);
        for (const [u, v] of edges) {
            g[u].push(v);
            g[v].push(u);
        }
        const bfsFarthest = (src) => {
            const dist = new Array(n).fill(-1);
            dist[src] = 0;
            const q = [src];
            let head = 0;
            let far = src;
            while (head < q.length) {
                const u = q[head++];
                if (dist[u] > dist[far]) far = u;
                for (const v of g[u]) {
                    if (dist[v] === -1) {
                        dist[v] = dist[u] + 1;
                        q.push(v);
                    }
                }
            }
            return [far, dist[far]];
        };
        const [a] = bfsFarthest(0);
        const [, d] = bfsFarthest(a);
        return d;
    };
    const d1 = treeDiameter(edges1);
    const d2 = treeDiameter(edges2);
    const combined = ((d1 + 1) >> 1) + ((d2 + 1) >> 1) + 1;
    return Math.max(d1, d2, combined);
}

class Solution {
    public int minimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
        int d1 = treeDiameter(edges1);
        int d2 = treeDiameter(edges2);
        int combined = (d1 + 1) / 2 + (d2 + 1) / 2 + 1;
        return Math.max(Math.max(d1, d2), combined);
    }

    private int treeDiameter(int[][] edges) {
        int n = edges.length + 1;
        if (n == 1) return 0;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) {
            g.get(e[0]).add(e[1]);
            g.get(e[1]).add(e[0]);
        }
        int[] a = bfsFarthest(g, 0, n);
        int[] b = bfsFarthest(g, a[0], n);
        return b[1];
    }

    private int[] bfsFarthest(List<List<Integer>> g, int src, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[src] = 0;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(src);
        int far = src;
        while (!q.isEmpty()) {
            int u = q.poll();
            if (dist[u] > dist[far]) far = u;
            for (int v : g.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.offer(v);
                }
            }
        }
        return new int[]{far, dist[far]};
    }
}

function minimumDiameterAfterMerge(edges1: number[][], edges2: number[][]): number {
    const treeDiameter = (edges: number[][]): number => {
        const n = edges.length + 1;
        if (n === 1) return 0;
        const g: number[][] = Array.from({ length: n }, () => []);
        for (const [u, v] of edges) {
            g[u].push(v);
            g[v].push(u);
        }
        const bfsFarthest = (src: number): [number, number] => {
            const dist: number[] = new Array(n).fill(-1);
            dist[src] = 0;
            const q: number[] = [src];
            let head = 0;
            let far = src;
            while (head < q.length) {
                const u = q[head++];
                if (dist[u] > dist[far]) far = u;
                for (const v of g[u]) {
                    if (dist[v] === -1) {
                        dist[v] = dist[u] + 1;
                        q.push(v);
                    }
                }
            }
            return [far, dist[far]];
        };
        const [a] = bfsFarthest(0);
        const [, d] = bfsFarthest(a);
        return d;
    };
    const d1 = treeDiameter(edges1);
    const d2 = treeDiameter(edges2);
    const combined = ((d1 + 1) >> 1) + ((d2 + 1) >> 1) + 1;
    return Math.max(d1, d2, combined);
}

Editorial#

Diameter of a tree is found by the two-BFS trick: any farthest node from an arbitrary start is one endpoint; the farthest from that endpoint is the other. To merge: the best joining edge lands at radii (ceil(d/2)) of each tree so that the new tree’s longest path through the bridge is balanced — that’s why the third term uses ceiling halves plus one for the new edge.

Complexity#

Time: O(n + m).
Space: O(n + m).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#