LeetCode 3203 - Find Minimum Diameter After Merging Two Trees

We are given two separate undirected trees. The first tree contains n nodes and is represented by edges1, while the second tree contains m nodes and is represented by edges2. A tree is a connected graph with no cycles.

leetcodehardtreedepth-first-searchbreadth-first-searchgraph-theory

LeetCode Problem 3203

Difficulty: 🔴 Hard
Topics: Tree, Depth-First Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

We are given two separate undirected trees. The first tree contains n nodes and is represented by edges1, while the second tree contains m nodes and is represented by edges2.

A tree is a connected graph with no cycles. Since each tree has exactly nodes - 1 edges, the input already guarantees that both graphs are valid trees.

We are allowed to add exactly one new edge that connects any node from the first tree to any node from the second tree. After adding this edge, the two trees become a single larger tree.

The goal is to minimize the diameter of this merged tree.

The diameter of a tree is the number of edges in the longest path between any two nodes. For example:

  • A single node has diameter 0
  • A chain of 4 nodes has diameter 3
  • A star centered at one node has diameter 2

The challenge is not merely computing the diameters of the original trees. We must determine the best pair of nodes to connect so that the resulting diameter is as small as possible.

The constraints are very large:

  • Up to 10^5 nodes per tree
  • Linear sized edge lists
  • Total graph size can exceed 2 * 10^5

This immediately tells us that any solution worse than linear or near linear time will likely time out.

Several edge cases are important:

  • One or both trees may contain only a single node
  • Trees may already have very small diameters
  • Trees may be highly unbalanced, such as long chains
  • Connecting arbitrary nodes is allowed, so the optimal connection point matters significantly
  • Since the graph is a tree, there is exactly one simple path between any two nodes

A naive solution that tries every possible pair of nodes would be far too slow because there can be up to 10^10 possible connections.

Approaches

Brute Force Approach

The brute force strategy is to try every possible connection between the two trees.

Suppose the first tree has n nodes and the second tree has m nodes. We could:

  1. Iterate through every node u in the first tree
  2. Iterate through every node v in the second tree
  3. Add an edge between u and v
  4. Compute the diameter of the resulting merged tree
  5. Keep the minimum diameter found

Computing the diameter of a tree can be done with two BFS or DFS traversals in linear time.

However, there are n * m possible node pairs. Since each diameter computation takes O(n + m) time, the total complexity becomes:

$$O(n \cdot m \cdot (n + m))$$

With up to 10^5 nodes, this is completely infeasible.

Key Insight

The critical observation is that the optimal connection points are the centers of the trees.

For any tree:

  • The diameter is the longest path
  • The center lies in the middle of that diameter
  • The maximum distance from the center to any node is called the radius

If a tree has diameter d, its radius is:

$$\left\lceil \frac{d}{2} \right\rceil$$

When we connect two trees optimally, the longest path in the merged tree can come from three possibilities:

  1. A path entirely inside the first tree
  2. A path entirely inside the second tree
  3. A path that crosses the new connecting edge

The third case is minimized when we connect the centers of the two trees.

If:

  • d1 is the diameter of the first tree
  • d2 is the diameter of the second tree

then the best possible merged diameter is:

$$\max(d1, d2, \lceil d1/2 \rceil + \lceil d2/2 \rceil + 1)$$

So the problem reduces to computing the diameters of the two trees efficiently.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m * (n + m)) O(n + m) Tries every possible connection
Optimal O(n + m) O(n + m) Uses tree diameter and radius properties

Algorithm Walkthrough

Step 1: Build the Adjacency List

Convert each edge list into an adjacency list representation.

Since the graph is undirected, every edge [u, v] is added in both directions:

  • u -> v
  • v -> u

An adjacency list is ideal because:

  • Trees are sparse graphs
  • Total edges are linear
  • DFS and BFS traversals become efficient

Step 2: Compute the Diameter of a Tree

We use the classic two pass BFS/DFS technique.

For any tree:

  1. Start DFS from an arbitrary node
  2. Find the farthest node from it
  3. Start another DFS from that farthest node
  4. The maximum distance found in the second DFS is the diameter

This works because in a tree, one endpoint of the diameter is always the farthest node from any arbitrary starting node.

Step 3: Compute the Radius of Each Tree

Once the diameter is known:

$$radius = \left\lceil \frac{diameter}{2} \right\rceil$$

In integer arithmetic:

radius = (diameter + 1) // 2

The radius represents the minimum possible maximum distance from the chosen connection node to all other nodes.

Step 4: Compute the Best Possible Merged Diameter

After connecting the centers:

$$merged = radius1 + radius2 + 1$$

The final diameter must account for:

  • Existing diameter in tree 1
  • Existing diameter in tree 2
  • New cross tree path

So the answer is:

$$\max(d1, d2, merged)$$

Why it works

The center of a tree minimizes the maximum distance to all nodes in that tree. Any path crossing between the two trees must travel:

  1. From a node in tree 1 to the connection point
  2. Across the new edge
  3. From the connection point in tree 2 to another node

Choosing the centers minimizes this worst case path. Therefore, connecting the centers produces the smallest possible merged diameter.

Python Solution

from typing import List
from collections import deque

class Solution:
    def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:

        def build_graph(edges: List[List[int]]) -> List[List[int]]:
            n = len(edges) + 1
            graph = [[] for _ in range(n)]

            for u, v in edges:
                graph[u].append(v)
                graph[v].append(u)

            return graph

        def bfs_farthest(start: int, graph: List[List[int]]):
            n = len(graph)
            visited = [False] * n

            queue = deque([(start, 0)])
            visited[start] = True

            farthest_node = start
            max_distance = 0

            while queue:
                node, dist = queue.popleft()

                if dist > max_distance:
                    max_distance = dist
                    farthest_node = node

                for neighbor in graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append((neighbor, dist + 1))

            return farthest_node, max_distance

        def get_diameter(edges: List[List[int]]) -> int:
            graph = build_graph(edges)

            farthest_node, _ = bfs_farthest(0, graph)

            _, diameter = bfs_farthest(farthest_node, graph)

            return diameter

        diameter1 = get_diameter(edges1)
        diameter2 = get_diameter(edges2)

        radius1 = (diameter1 + 1) // 2
        radius2 = (diameter2 + 1) // 2

        merged_diameter = radius1 + radius2 + 1

        return max(diameter1, diameter2, merged_diameter)

The implementation begins by constructing adjacency lists for both trees. Since trees are undirected, every edge is inserted in both directions.

The bfs_farthest helper performs a breadth first search and returns two values:

  • The farthest node reached
  • The distance to that node

This helper is used twice inside get_diameter.

The first BFS starts from an arbitrary node, node 0, and identifies one endpoint of the diameter. The second BFS starts from that endpoint and measures the actual diameter.

After obtaining both diameters, the code computes the radii using integer arithmetic. Finally, it applies the optimal formula:

max(d1, d2, r1 + r2 + 1)

This guarantees the smallest possible merged diameter.

Go Solution

package main

func minimumDiameterAfterMerge(edges1 [][]int, edges2 [][]int) int {

	buildGraph := func(edges [][]int) [][]int {
		n := len(edges) + 1
		graph := make([][]int, n)

		for _, edge := range edges {
			u, v := edge[0], edge[1]
			graph[u] = append(graph[u], v)
			graph[v] = append(graph[v], u)
		}

		return graph
	}

	type Pair struct {
		node int
		dist int
	}

	bfsFarthest := func(start int, graph [][]int) (int, int) {
		n := len(graph)

		visited := make([]bool, n)
		queue := []Pair{{start, 0}}
		visited[start] = true

		farthestNode := start
		maxDistance := 0

		for len(queue) > 0 {
			current := queue[0]
			queue = queue[1:]

			node := current.node
			dist := current.dist

			if dist > maxDistance {
				maxDistance = dist
				farthestNode = node
			}

			for _, neighbor := range graph[node] {
				if !visited[neighbor] {
					visited[neighbor] = true
					queue = append(queue, Pair{neighbor, dist + 1})
				}
			}
		}

		return farthestNode, maxDistance
	}

	getDiameter := func(edges [][]int) int {
		graph := buildGraph(edges)

		farthestNode, _ := bfsFarthest(0, graph)

		_, diameter := bfsFarthest(farthestNode, graph)

		return diameter
	}

	diameter1 := getDiameter(edges1)
	diameter2 := getDiameter(edges2)

	radius1 := (diameter1 + 1) / 2
	radius2 := (diameter2 + 1) / 2

	mergedDiameter := radius1 + radius2 + 1

	return max(diameter1, max(diameter2, mergedDiameter))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation follows the same algorithmic structure as the Python version.

A custom Pair struct is used to store BFS state inside the queue. Go slices are used as adjacency lists.

Unlike Python, Go does not provide a built in deque structure, so the queue is implemented using slice operations.

Integer division in Go automatically truncates toward zero, which matches the desired behavior for radius computation.

Worked Examples

Example 1

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

Step 1: Compute Diameter of First Tree

The first tree looks like:

    1
    |
2 - 0 - 3

Start BFS from node 0.

Node Reached Distance
0 0
1 1
2 1
3 1

One farthest node is 1.

Now BFS from node 1.

Node Reached Distance
1 0
0 1
2 2
3 2

Diameter of first tree:

d1 = 2

Radius:

r1 = (2 + 1) // 2 = 1

Step 2: Compute Diameter of Second Tree

Tree:

0 - 1

Diameter:

d2 = 1

Radius:

r2 = (1 + 1) // 2 = 1

Step 3: Merge Formula

merged = r1 + r2 + 1
        = 1 + 1 + 1
        = 3

Final answer:

max(2, 1, 3) = 3

Example 2

Both trees are identical.

Diameter of each tree:

d1 = 4
d2 = 4

Radius of each tree:

r1 = 2
r2 = 2

Merged diameter:

2 + 2 + 1 = 5

Final answer:

max(4, 4, 5) = 5

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each tree is traversed a constant number of times
Space O(n + m) Adjacency lists, visited arrays, and BFS queue

Each tree requires:

  • Building the adjacency list in linear time
  • Two BFS traversals for diameter computation

Since every node and edge is processed only a constant number of times, the total runtime remains linear.

The space usage is also linear because we store adjacency lists and traversal state.

Test Cases

from typing import List

sol = Solution()

# Example 1
assert sol.minimumDiameterAfterMerge(
    [[0,1],[0,2],[0,3]],
    [[0,1]]
) == 3  # star tree merged with single edge tree

# Example 2
assert sol.minimumDiameterAfterMerge(
    [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]],
    [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]
) == 5  # identical balanced trees

# Both trees are single nodes
assert sol.minimumDiameterAfterMerge([], []) == 1  # one connecting edge only

# One chain and one single node
assert sol.minimumDiameterAfterMerge(
    [[0,1],[1,2],[2,3]],
    []
) == 4  # merged diameter equals original chain diameter

# Two chains
assert sol.minimumDiameterAfterMerge(
    [[0,1],[1,2]],
    [[0,1],[1,2]]
) == 3  # optimal center connection

# Highly unbalanced trees
assert sol.minimumDiameterAfterMerge(
    [[0,1],[1,2],[2,3],[3,4]],
    [[0,1]]
) == 5  # long chain dominates

# Small star trees
assert sol.minimumDiameterAfterMerge(
    [[0,1],[0,2]],
    [[0,1],[0,2]]
) == 3  # center to center merge

# Large diameter preservation
assert sol.minimumDiameterAfterMerge(
    [[0,1],[1,2],[2,3],[3,4],[4,5]],
    [[0,1]]
) == 6  # original diameter remains largest

Test Summary

Test Why
Example 1 Validates star shaped tree behavior
Example 2 Validates balanced large trees
Two single nodes Smallest possible input
Chain and single node Ensures existing diameter can dominate
Two chains Verifies center connection logic
Highly unbalanced trees Tests long path handling
Small star trees Tests radius based merging
Large diameter preservation Ensures formula handles dominant tree

Edge Cases

Single Node Trees

A tree may contain only one node, represented by an empty edge list.

This case is easy to mishandle because BFS implementations often assume at least one edge exists. In this solution, the number of nodes is computed as len(edges) + 1, so an empty edge list correctly produces a graph with one node.

The diameter of a single node tree is correctly computed as 0.

Very Long Chain Trees

A tree shaped like a linked list has the maximum possible diameter for its size.

For example:

0 - 1 - 2 - 3 - 4

Naive recursive DFS implementations may risk recursion depth issues in Python for large inputs. This solution avoids that problem entirely by using iterative BFS.

The algorithm still runs in linear time even for the worst possible tree shape.

One Tree Dominates the Final Diameter

Sometimes the merged path is not the largest path.

For example:

  • Tree 1 diameter = 10
  • Tree 2 diameter = 1

Even after optimal merging, the resulting diameter may still be 10.

This is why the final answer is:

max(d1, d2, merged)

instead of simply returning the merged path length.

Without this check, the implementation would incorrectly underestimate the final diameter.