3203. Find Minimum Diameter After Merging Two Trees

Tree Depth-First Search Breadth-First Search Graph

Time: O(n + m)

Space: O(n + m)

Approach

Find diameter of each tree via BFS; merged diameter = max(d1, d2, ceil(d1/2)+ceil(d2/2)+1).

Key Techniques

Tree problems typically require recursive DFS or iterative BFS. Common patterns: preorder for serialization, inorder for BST sorted output, postorder for bottom-up aggregation. Always consider edge cases: null nodes, single-node trees, and skewed (list-like) trees.

Depth-First Search

DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.

Breadth-First Search

BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.

3203.cs

// Approach: Find diameter of each tree via BFS; merged diameter = max(d1, d2, ceil(d1/2)+ceil(d2/2)+1).
// Time: O(n + m) Space: O(n + m)

public class Solution
{
    public int MinimumDiameterAfterMerge(int[][] edges1, int[][] edges2)
    {
        int diameter1 = GetDiameter(edges1);
        int diameter2 = GetDiameter(edges2);
        int combinedDiameter = (diameter1 + 1) / 2 + (diameter2 + 1) / 2 + 1;
        return Math.Max(Math.Max(diameter1, diameter2), combinedDiameter);
    }

    private int GetDiameter(int[][] edges)
    {
        int n = edges.Length + 1;
        List<int>[] graph = new List<int>[n];

        for (int i = 0; i < n; i++)
            graph[i] = new List<int>();

        foreach (int[] edge in edges)
        {
            int u = edge[0];
            int v = edge[1];
            graph[u].Add(v);
            graph[v].Add(u);
        }

        int[] maxDiameter = new int[1];
        MaxDepth(graph, 0, -1, maxDiameter);
        return maxDiameter[0];
    }

    private int MaxDepth(List<int>[] graph, int u, int prev, int[] maxDiameter)
    {
        int maxSubDepth1 = 0;
        int maxSubDepth2 = 0;
        foreach (int v in graph[u])
        {
            if (v == prev)
                continue;
            int maxSubDepth = MaxDepth(graph, v, u, maxDiameter);
            if (maxSubDepth > maxSubDepth1)
            {
                maxSubDepth2 = maxSubDepth1;
                maxSubDepth1 = maxSubDepth;
            }
            else if (maxSubDepth > maxSubDepth2)
                maxSubDepth2 = maxSubDepth;
        }

        maxDiameter[0] = Math.Max(maxDiameter[0], maxSubDepth1 + maxSubDepth2);
        return 1 + maxSubDepth1;
    }
}

Was this solution helpful?