3203. Find Minimum Diameter After Merging Two Trees

Intuition

The problem requires connecting two trees such that the resulting tree has the minimum possible diameter. The diameter of a tree is defined as the longest path between any two nodes in the tree. To minimize the diameter after connecting two trees, we need to strategically choose nodes from each tree to connect.

Approach

1. Calculate Tree Diameters: First, compute the diameters of both trees: - Use Depth-First Search (DFS) to find the diameter of each tree. Start from an arbitrary node (often node 0 for simplicity).
2. Connecting Trees: After obtaining the diameters (d1 for the first tree and d2 for the second tree), the possible diameters of the resulting tree are: - d1 + d2 + 1: This accounts for the worst-case scenario where the longest path in the resulting tree goes through the connecting edge.
3. Choose Connecting Nodes: To achieve the minimum diameter, connect nodes that minimize the impact on the existing diameters. A strategic choice is often connecting the centroid or a node close to the centroid of each tree.
4. Compute Minimum Diameter: Calculate the possible diameters resulting from connecting different pairs of nodes from both trees and choose the minimum diameter.
5. Implementation Details: Implement DFS to calculate tree diameters and carefully choose nodes for connection to minimize the resulting diameter. Edge cases include trees with minimal nodes (like single-node trees).

Complexity

• Time Complexity: - Calculating tree diameters using DFS: \( O(n) \) for the first tree and \( O(m) \) for the second tree, where \( n \) and \( m \) are the number of nodes in each tree. - Overall, the time complexity is \( O(n + m) \).
• Space Complexity: - Additional space for storing adjacency lists and recursive call stack during DFS: \( O(n + m) \).

This approach ensures that we find the optimal way to connect the two trees while minimizing the diameter of the resulting tree efficiently.

Code Explanation

var minimumDiameterAfterMerge = function (edges1, edges2) {

• Defines a function minimumDiameterAfterMerge that takes two arguments, edges1 and edges2.

    var getDiameter = (edges) => {

• Defines an inner function getDiameter that calculates the diameter of a tree given its edges.

let map = Array(edges.length + 1)
  .fill()
  .map(() => []);

• Creates an adjacency list map to represent the graph. It initializes an array of empty arrays.

for (let [i, j] of edges) {
  map[i].push(j);
  map[j].push(i);
}

• Fills the adjacency list by iterating over each edge [i, j] and adding j to the list of neighbors of i and vice versa.

let res = 0;

• Initializes a variable res to store the maximum diameter found.

        var dfs = (node, parent) => {
            let maxDepth = 1;

• Defines a depth-first search (DFS) function dfs that calculates the depth of the tree and updates the diameter. It initializes maxDepth to 1.

            for (let neighbor of map[node]) {
                if (neighbor === parent) continue;
                let depth = dfs(neighbor, node);
                res = Math.max(res, maxDepth + depth);
                maxDepth = Math.max(maxDepth, 1 + depth);
            }
            return maxDepth;
        };

• Iterates over the neighbors of the current node. If the neighbor is the parent, it continues to the next iteration. It calculates the depth by recursively calling dfs on the neighbor. Updates res with the maximum diameter found so far. Updates maxDepth with the maximum depth found so far. Returns maxDepth.

dfs(0, -1);

• Calls the dfs function starting from node 0 with -1 as the parent.

        return res;
    };

• Returns the diameter of the tree.

let d1 = getDiameter(edges1);
let d2 = getDiameter(edges2);

• Calculates the diameters of the two trees, d1 and d2.

    return Math.max(d1 - 1, d2 - 1, Math.floor(d1 / 2) + Math.floor(d2 / 2) + 1);
};

• Returns the maximum diameter after merging the two trees. The formula calculates the possible maximum diameter by considering the largest tree and the sum of half-diameters of both trees plus one.

Code

C++

class Solution {
public:
    int minimumDiameterAfterMerge(vector>& edges1, vector>& edges2) {
        int d1 = getDiameter(edges1);
        int d2 = getDiameter(edges2);
        return max(max(d1 - 1, d2 - 1), d1 / 2 + d2 / 2 + 1);
    }

private:
    int getDiameter(vector>& edges) {
        unordered_map> map;
        for (auto& edge : edges) {
            int i = edge[0];
            int j = edge[1];
            map[i].push_back(j);
            map[j].push_back(i);
        }

        int res = 0;
        dfs(0, -1, map, res);

        return res;
    }

    int dfs(int node, int parent, unordered_map>& map, int& res) {
        int maxDepth = 1;
        for (int neighbor : map[node]) {
            if (neighbor == parent)
                continue;
            int depth = dfs(neighbor, node, map, res);
            res = max(res, maxDepth + depth);
            maxDepth = max(maxDepth, 1 + depth);
        }
        return maxDepth;
    }
};

Python

class Solution:
    def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
        def getDiameter(edges):
            map = defaultdict(list)
            for i, j in edges:
                map[i].append(j)
                map[j].append(i)
            
            res = [0]
            
            def dfs(node, parent):
                maxDepth = 1
                for neighbor in map[node]:
                    if neighbor == parent:
                        continue
                    depth = dfs(neighbor, node)
                    res[0] = max(res[0], maxDepth + depth)
                    maxDepth = max(maxDepth, 1 + depth)
                return maxDepth
            
            dfs(0, -1)
            
            return res[0]
        
        d1 = getDiameter(edges1)
        d2 = getDiameter(edges2)
        
        return max(d1 - 1, d2 - 1, d1 // 2 + d2 // 2 + 1)

Java

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

    private int getDiameter(int[][] edges) {
        List> map = new ArrayList<>();
        for (int i = 0; i < edges.length + 1; i++) {
            map.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int i = edge[0];
            int j = edge[1];
            map.get(i).add(j);
            map.get(j).add(i);
        }

        int[] res = { 0 };

        dfs(0, -1, map, res);

        return res[0];
    }

    private int dfs(int node, int parent, List> map, int[] res) {
        int maxDepth = 1;
        for (int neighbor : map.get(node)) {
            if (neighbor == parent)
                continue;
            int depth = dfs(neighbor, node, map, res);
            res[0] = Math.max(res[0], maxDepth + depth);
            maxDepth = Math.max(maxDepth, 1 + depth);
        }
        return maxDepth;
    }
}

JavaScript

/**
 * @param {number[][]} edges1
 * @param {number[][]} edges2
 * @return {number}
 */
var minimumDiameterAfterMerge = function (edges1, edges2) {
    var getDiameter = (edges) => {
        let map = Array(edges.length + 1).fill().map(() => []);

        for (let [i, j] of edges) {
            map[i].push(j);
            map[j].push(i);
        }

        let res = 0;

        var dfs = (node, parent) => {
            let maxDepth = 1;
            for (let neighbor of map[node]) {
                if (neighbor === parent) continue;
                let depth = dfs(neighbor, node);
                res = Math.max(res, maxDepth + depth);
                maxDepth = Math.max(maxDepth, 1 + depth);
            }
            return maxDepth;
        };

        dfs(0, -1);

        return res;
    };

    let d1 = getDiameter(edges1);
    let d2 = getDiameter(edges2);

    return Math.max(d1 - 1, d2 - 1, Math.floor(d1 / 2) + Math.floor(d2 / 2) + 1);
};