Vultr DocsLatest Content

Find Minimum Diameter After Merging Two Trees

Updated on 30 May, 2025
Find Minimum Diameter After Merging Two Trees header image

Problem Statement

In this scenario, you are given two undirected trees, each defined by a set of edges and nodes. The first tree comprises n nodes labeled from 0 to n-1 with edges defined in an array edges1. Each entry edges1[i] = [ai, bi] represents an edge connecting nodes ai and bi. Similarly, the second tree has m nodes, labeled from 0 to m-1, with connections detailed in the array edges2, where each edges2[i] = [ui, vi] defines the edge between ui and vi.

Your main objective is to link any node from the first tree with any node from the second tree via a single new edge. This connection should result in a combined tree whose structure minimizes the diameter. The diameter is defined as the greatest distance (i.e., the longest path) between any two nodes within the tree.

The challenge lies in determining which nodes from each tree to connect to achieve the smallest possible diameter in the resulting combined tree structure.

Examples

Example 1

Input:

edges1 = [[0,1],[0,2],[0,3]]
edges2 = [[0,1]]

Output:

3

Explanation:

We can obtain a tree of diameter 3 by connecting node 0 from the first tree with any node from the second tree.

Example 2

Input:

edges1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]
edges2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]

Output:

5

Explanation:

We can obtain a tree of diameter 5 by connecting node 0 from the first tree with node 0 from the second tree.

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 <= ai, bi < n
  • edges2[i] = [ui, vi]
  • 0 <= ui, vi < m
  • The input is generated such that edges1 and edges2 represent valid trees.

Approach and Intuition

Given the need to minimize the diameter of a combined tree formed by linking two separate trees, here is a strategic approach broken down into detailed steps:

  1. Understand and Calculate Individual Tree Diameters:

    • Compute the diameter for both trees independently. The diameter is the longest path between any two nodes. This can be efficiently found by:

      • Choosing an arbitrary node and using BFS or DFS to find the farthest node from it, say A.
      • Running BFS/DFS again from A to find the farthest node from A, say B.
      • The distance between A and B is the diameter of the tree.

  2. Evaluate Potential Connections:

    • For each tree, determine the nodes that are involved in their respective diameters as potential candidates for connection. From the definition of tree diameter, the ends of the diameter paths might be the best candidates for connection.

  3. Simulate Different Connections:

    • Consider connecting differing pairs of end nodes from the two tree diameters calculated in the first step. For each pair, simulate what the resulting diameter would be if these nodes were connected.

  4. Compute Combined Tree Diameter:

    • For each potential new combined tree formed in the previous step, calculate the diameter using the nodes involved in the connection:

      • The new potential diameter of the combined tree would usually be the maximum of:

        • The diameter of the first tree.
        • The diameter of the second tree.
        • The sum of half the diameters of both trees (rounded up) plus one (to account for the new connecting edge).

  5. Determine Minimum Diameter:

    • Among all the diameters calculated by connecting different node pairs, select the minimum diameter configuration.

The insight here is to effectively leverage the properties of the trees’ structure, especially the endpoints of their diameters, to explore minimal length pathways in the combined tree.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int minDiameterMerge(vector<vector<int>>& tree1, vector<vector<int>>& tree2) {
        int treeNodes1 = tree1.size() + 1;
        int treeNodes2 = tree2.size() + 1;

        vector<vector<int>> graph1 = constructGraph(treeNodes1, tree1);
        vector<vector<int>> graph2 = constructGraph(treeNodes2, tree2);

        int treeDiameter1 = calculateDiameter(treeNodes1, graph1);
        int treeDiameter2 = calculateDiameter(treeNodes2, graph2);

        cout << treeDiameter1 << " " << treeDiameter2 << "\n";

        int combinedTreeDiameter = ceil(treeDiameter1 / 2.0) + ceil(treeDiameter2 / 2.0) + 1;

        return max({treeDiameter1, treeDiameter2, combinedTreeDiameter});
    }

private:
    vector<vector<int>> constructGraph(int count, vector<vector<int>>& edges) {
        vector<vector<int>> adjacencyList(count);
        for (auto& edge : edges) {
            adjacencyList[edge[0]].push_back(edge[1]);
            adjacencyList[edge[1]].push_back(edge[0]);
        }
        return adjacencyList;
    }

    int calculateDiameter(int count, vector<vector<int>>& adjacencyList) {
        queue<int> leafQueue;
        vector<int> nodeDegrees(count);
        
        for (int node = 0; node < count; node++) {
            nodeDegrees[node] = adjacencyList[node].size();
            if (nodeDegrees[node] == 1) {
                leafQueue.push(node);
            }
        }

        int currentNodes = count;
        int layersRemoved = 0;

        while (currentNodes > 2) {
            int leavesCount = leafQueue.size();
            currentNodes -= leavesCount;
            layersRemoved++;

            for (int i = 0; i < leavesCount; i++) {
                int currentNode = leafQueue.front();
                leafQueue.pop();

                for (int neighbor : adjacencyList[currentNode]) {
                    nodeDegrees[neighbor]--;
                    if (nodeDegrees[neighbor] == 1) {
                        leafQueue.push(neighbor);
                    }
                }
            }
        }

        if (currentNodes == 2) return 2 * layersRemoved + 1;
        return 2 * layersRemoved;
    }
};

This solution involves computing the minimum diameter possible after merging two trees represented as adjacency lists in the provided C++ code. The merging strategy provided ensures that the optimum connection point between the two trees is chosen to potentially reduce the overall diameter.

  • Begin by computing the number of nodes in each tree by adding one to the size of the input tree edge lists, as the trees are likely represented one index short (0-based index).
  • Use constructGraph function to convert edge lists into adjacency lists for both trees, which helps simplify graph traversal and operation.
  • Calculate the diameter of each individual tree using the calculateDiameter function. This function employs a level-by-level traversal (using BFS) to peel off leaf nodes layer by layer until one or two central nodes remain, which determines the tree's diameter.
  • Calculate the potential combined diameter if the trees are connected optimally. The combined diameter considers half the diameter of each tree (rounded up) plus one additional edge that represents the joining edge.
  • Decide the final output by taking the maximum diameter among the individual diameters of the two trees and the calculated combined diameter. This approach ensures that the final solution respects the largest unavoidable diameter while exploring possible optimality in combining the trees.

The calculateDiameter function operates by progressively eliminating leaf nodes until only one or two nodes remain. This method exploits the property that the tree diameter can be visualized as the longest path between the farthest two leaf nodes, which can alternatively be found by reducing the tree around its centroid.

Overall, this C++ code implements an effective method to determine the minimum diameter of a merged tree structure by leveraging graph traversal techniques and properties of tree diameters. Ensure to understand the tree structure and diameter properties, as well as basic graph manipulation techniques to fully utilize this solution.

java 
class Solution {

    public int minDiameterAfterCombination(int[][] tree1Edges, int[][] tree2Edges) {
        // Determine the total nodes in both trees
        int nodesCount1 = tree1Edges.length + 1;
        int nodesCount2 = tree2Edges.length + 1;

        // Construct adjacency list representation for both trees
        List<List<Integer>> adjacency1 = buildList(nodesCount1, tree1Edges);
        List<List<Integer>> adjacency2 = buildList(nodesCount2, tree2Edges);

        // Calculate tree diameters
        int tree1Diameter = calculateDiameter(nodesCount1, adjacency1);
        int tree2Diameter = calculateDiameter(nodesCount2, adjacency2);

        // Determine longest path across both trees
        int crossDiameter =
            (int) Math.ceil(tree1Diameter / 2.0) +
            (int) Math.ceil(tree2Diameter / 2.0) +
            1;

        // Final comparison to return the largest diameter possible
        return Math.max(Math.max(tree1Diameter, tree2Diameter), crossDiameter);
    }

    // Create adjacency list for graph representation from given edges
    private List<List<Integer>> buildList(int count, int[][] edges) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            list.get(edge[0]).add(edge[1]);
            list.get(edge[1]).add(edge[0]);
        }
        return list;
    }

    // Measure the diameter of the tree using layered leaf removal method
    private int calculateDiameter(int nodeCount, List<List<Integer>> adjacency) {
        Queue<Integer> queue = new LinkedList<>();
        int[] nodeDegrees = new int[nodeCount];

        // Initialize degrees and enqueue initial leaves
        for (int i = 0; i < nodeCount; i++) {
            nodeDegrees[i] = adjacency.get(i).size();
            if (nodeDegrees[i] == 1) {
                queue.offer(i);
            }
        }

        int nodesRemaining = nodeCount;
        int layersRemoved = 0;

        // Remove leaves layer-by-layer until 2 or fewer nodes remain
        while (nodesRemaining > 2) {
            int currentSize = queue.size();
            nodesRemaining -= currentSize;
            layersRemoved++;

            for (int i = 0; i < currentSize; i++) {
                int leafNode = queue.poll();
                for (int neighbor : adjacency.get(leafNode)) {
                    nodeDegrees[neighbor]--;
                    if (nodeDegrees[neighbor] == 1) {
                        queue.offer(neighbor);
                    }
                }
            }
        }

        // Calculate the diameter based on the remaining nodes
        if (nodesRemaining == 2) return 2 * layersRemoved + 1;
        
        return 2 * layersRemoved;
    }
}

To solve the problem of finding the minimum diameter after merging two trees, the Java program defines a function minDiameterAfterCombination that takes as input the edge lists of two trees and outputs the minimum diameter possible post-merger. Here's how the solution approaches the problem:

  1. First, calculate the total number of nodes in both trees based on their edge lists.
  2. Create adjacency lists for both trees to represent their structure, which facilitates the later calculations.
  3. Calculate the diameter of both input trees independently. This is done using a method called calculateDiameter, which employs the "layered leaf removal method." This method involves progressively removing leaf nodes from the tree and counting the layers removed until only one or two nodes remain.
  4. Compute the maximum diameter that could be achieved if a single edge connection was made between the two trees. This is calculated by combining half the diameters of the two trees (rounded up) and adding one (to account for the connecting edge).
  5. The final minimum diameter after the potential merging of the two trees is the maximum value among the diameters of the individual trees and the estimated diameter if connected.

The helper functions buildList and calculateDiameter are integral to the implementation:

  • buildList constructs an adjacency list from given edge data. This list facilitates the traversal and manipulation needed to calculate tree diameters.
  • calculateDiameter imparts the core logic to determine the diameter of a tree using breadth-first traversal, counting node degrees, and systematically removing leaf nodes.

This structured approach ensures efficiency in deriving the minimal diameter possible through optimal merging of the trees, considering both individual and combined structures.

python 
class Solution:
    def minimumDiameterMerge(self, edgesSet1, edgesSet2):
        # Calculate nodes in each tree by incrementing edge count
        numNodes1 = len(edgesSet1) + 1
        numNodes2 = len(edgesSet2) + 1

        # Building adjacent lists for provided edge sets
        adjacency1 = self.create_adjacency(numNodes1, edgesSet1)
        adjacency2 = self.create_adjacency(numNodes2, edgesSet2)

        # Calculate diameters for constructed trees
        treeDiameter1 = self.calculate_diameter(numNodes1, adjacency1)
        treeDiameter2 = self.calculate_diameter(numNodes2, adjacency2)

        # Longest path through both trees
        crossDiameter = ceil(treeDiameter1 / 2) + ceil(treeDiameter2 / 2) + 1

        # Return maximum value among individual and combined diameter
        return max(treeDiameter1, treeDiameter2, crossDiameter)

    # Helper to build adjacency list using size and edges
    def create_adjacency(self, size, edges):
        list_adj = [[] for _ in range(size)]
        for edge in edges:
            list_adj[edge[0]].append(edge[1])
            list_adj[edge[1]].append(edge[0])
        return list_adj

    # Helper to compute the tree diameter using BFS layer expansion
    def calculate_diameter(self, nodeCount, adjacency):
        queue_leaves = deque()
        node_degrees = [0] * nodeCount

        # Initialize node degrees and identify initial leaf nodes
        for node in range(nodeCount):
            node_degrees[node] = len(adjacency[node])
            if node_degrees[node] == 1:
                queue_leaves.append(node)

        nodesLeft = nodeCount
        layersRemoved = 0

        # BFS to remove leaf layers until we reach core structure
        while nodesLeft > 2:
            layerSize = len(queue_leaves)
            nodesLeft -= layerSize
            layersRemoved += 1

            for _ in range(layerSize):
                leaf = queue_leaves.popleft()
                for neighbor in adjacency[leaf]:
                    node_degrees[neighbor] -= 1
                    if node_degrees[neighbor] == 1:
                        queue_leaves.append(neighbor)

        if nodesLeft == 2:
            return 2 * layersRemoved + 1

        return 2 * layersRemoved

In this Python solution, the task is to compute the minimum diameter after merging two trees represented by sets of edges. The merged diameter consists of the maximum value among the individual diameters of the two trees and their cross diameter. The steps involved in achieving this include:

  • Calculate the number of nodes in each tree from the corresponding edges plus one.
  • Construct an adjacency list for both sets of edges to represent each tree’s structure.
  • Measure the diameter of each tree individually using breadth-first search (BFS) method for tree diameter calculation, which involves:
    • Initializing a dequeue for leaf layers and a list for node degrees.
    • Removing leaf nodes per BFS iteration until reaching the central core of the tree.
  • Compute the cross diameter, which is determined by the formula taking half the ceiling value of each tree's diameter, summed, plus one.
  • Return the maximum value among the two diameters and the cross diameter.

The functions include:

  • create_adjacency to build adjacency lists from the nodes and edges, facilitating the creation of an interconnected tree structure.
  • calculate_diameter to ascertain the tree's diameter through iterative leaf removal and layer counting, employing a BFS strategy.

This dynamic approach ensures a thorough tree analysis by handling structures and connectivity and determining optimal path measures dynamically through merged tree scenarios.

Comments

No comments yet.