We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Minimum Diameter After Merging Two Trees

Difficulty: Hard

Problem Description

There exist two undirected trees with n and m nodes, numbered from 0 to n - 1 and from 0 to m - 1, respectively. You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the first tree and edges2[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the second tree. You must connect one node from the first tree with another node from the second tree with an edge. Return the minimum possible diameter of the resulting tree. The diameter of a tree is the length of the longest path between any two nodes in the tree.

Key Insights

  • The diameter of a tree can be computed by finding the longest path between any two nodes, which can be determined using depth-first search (DFS) or breadth-first search (BFS).
  • Merging two trees involves considering the additional edge that can be formed by connecting any node from the first tree to any node from the second tree.
  • The minimum diameter after merging the trees can be calculated by considering the longest paths from the endpoints of the two trees and the distance to the new edge connecting them.

Space and Time Complexity

Time Complexity: O(n + m) - where n and m are the number of nodes in the respective trees, as we traverse each tree to calculate the diameters. Space Complexity: O(n + m) - for storing the graph representations of both trees and the recursion stack during DFS.

Solution

To solve this problem, we will use a depth-first search (DFS) approach to compute the diameter of each tree separately. The algorithm proceeds as follows:

  1. Construct the adjacency list for both trees from the provided edge lists.
  2. Use DFS to find the farthest node from an arbitrary starting node in each tree, which will give us one endpoint of the diameter.
  3. From this endpoint, perform another DFS to find the actual diameter of the tree.
  4. Repeat the process for the second tree.
  5. Finally, compute the minimum possible diameter after merging by considering the maximum distances found in both trees and the potential edge connecting them.

Code Solutions

def findDiameter(edges):
    from collections import defaultdict

    def dfs(node, parent):
        max_dist = 0
        for neighbor in graph[node]:
            if neighbor != parent:
                dist = dfs(neighbor, node) + 1
                max_dist = max(max_dist, dist)
        return max_dist

    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    # Start DFS from an arbitrary node, here we choose node 0
    farthest_node = dfs(0, -1)
    # Perform DFS again from the farthest node found
    diameter = dfs(farthest_node, -1)
    return diameter

def minDiameterAfterMerging(edges1, edges2):
    diameter1 = findDiameter(edges1)
    diameter2 = findDiameter(edges2)

    # The minimum possible diameter after merging
    return max(diameter1, diameter2) + 1

# Example usage
edges1 = [[0,1],[0,2],[0,3]]
edges2 = [[0,1]]
print(minDiameterAfterMerging(edges1, edges2))  # Output: 3
← Back to All Questions