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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Minimum Diameter After Merging Two Trees

Number: 3439

Difficulty: Hard

Paid? No

Companies: ServiceNow

Problem Description

Given two undirected trees (one with n nodes and the other with m nodes) represented by edge lists, you must connect one node from the first tree to one node from the second tree with an edge. The objective is to choose a connection that minimizes the diameter of the resulting tree. The diameter of a tree is defined as the length of the longest path between any two nodes in the tree.

Key Insights

  • The diameter of a tree can be computed using two BFS/DFS traversals: one to find an endpoint and the second to compute the farthest distance from that endpoint.
  • For any tree, the "radius" – the minimum possible maximum distance from a selected center node – is given by (diameter + 1) // 2.
  • When merging the two trees by connecting one node from each, the longest path may come from:
    • The diameter in the first tree.
    • The diameter in the second tree.
    • A combined path that goes from the farthest leaf in tree1 (from its center) to the farthest leaf in tree2 (from its center) plus the connecting edge.
  • Therefore, the minimum possible diameter of the merged tree is: max(diameter1, diameter2, radius1 + radius2 + 1)

Space and Time Complexity

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

Solution

We first compute the diameter for each tree using two traversals (BFS or DFS). For each tree:

  1. Start from an arbitrary node to perform a BFS/DFS to determine the farthest node.
  2. From that farthest node, perform another BFS/DFS to find the farthest distance which will be the tree's diameter.
  3. Calculate the radius as (diameter + 1) // 2. After obtaining diameters (and thus radii) for both trees, the answer is given by the maximum among the two diameters and (radius1 + radius2 + 1), where the additional 1 accounts for the connecting edge between the two trees.

Code Solutions

# Python solution
from collections import deque

def tree_diameter(n, edges):
    # Build the adjacency list for the tree
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Helper function: BFS that returns (farthest_node, distance, distances_array)
    def bfs(start):
        distances = [-1] * n
        distances[start] = 0
        queue = deque([start])
        farthest_node = start
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if distances[neighbor] == -1:
                    distances[neighbor] = distances[node] + 1
                    queue.append(neighbor)
                    if distances[neighbor] > distances[farthest_node]:
                        farthest_node = neighbor
        return farthest_node, distances[farthest_node], distances
    
    # First BFS from an arbitrary node (0)
    node_far, _, _ = bfs(0)
    # Second BFS from the farthest node found to get the diameter
    other_end, diameter, _ = bfs(node_far)
    return diameter

def find_minimum_diameter(edges1, edges2):
    n = len(edges1) + 1
    m = len(edges2) + 1

    # Compute diameters for both trees
    d1 = tree_diameter(n, edges1)
    d2 = tree_diameter(m, edges2)
    
    # Compute radii for the trees (using formula: (diameter + 1) // 2)
    r1 = (d1 + 1) // 2
    r2 = (d2 + 1) // 2

    # The answer is the maximum of the diameters of individual trees and the path that goes through the centers of the two trees
    return max(d1, d2, r1 + r2 + 1)

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