Find Minimum Diameter After Merging Two Trees solution and explanation
Google
9 more videos on this problem
Find Minimum Diameter After Merging Two Trees | Leetcode 3203 | Graph Concepts & Qns - 45 | MIKcodestorywithMIK · 29:52 · 11K views
Find Minimum Diameter After Merging Two Trees - Leetcode 3203 - PythonNeetCodeIO · 24:41 · 9K views
3203. Find Minimum Diameter After Merging Two Trees | Diameter of a Tree | GraphAryan Mittal · 23:43 · 6K views
Find Minimum Diameter After Merging Two Trees | Leetcode 3203Techdose · 19:41 · 3K views
3203. Find Minimum Diameter After Merging Two Trees | Leetcode Daily 24 Dec 2024 | Java | HindiAlgorithmHQ · 22:29 · 1K views
3203. Find Minimum Diameter After Merging Two Trees | Weekly Leetcode 404codingMohan · 48:51 · 958 views
Daily Leetcode #1729: Dec 24, 2024 - 3203. Find Minimum Diameter After Merging Two TreesProgramming Live with Larry · 11:18 · 488 views
3203. Find Minimum Diameter After Merging Two Trees || Leetcode POTDPrateek Goel · 13:53 · 353 views
3203. Find Minimum Diameter After Merging Two Trees (Leetcode Hard)Programming Live with Larry · 21:00 · 346 views
3203. Find Minimum Diameter After Merging Two Trees | Leetcode Daily Challenge | Problem of the dayEthos Typos · 24:23 · 222 views
The problem
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] = [ai, bi] indicates that there is an edge between nodes ai and bi in the first tree and edges2[i] = [ui, vi] indicates that there is an edge between nodes ui and vi 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.
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 <= 105edges1.length == n - 1edges2.length == m - 1edges1[i].length == edges2[i].length == 2edges1[i] = [ai, bi]0 <= ai, bi < nedges2[i] = [ui, vi]0 <= ui, vi < m- The input is generated such that
edges1andedges2represent valid trees.
Approach overview
Problem Overview: Two separate trees are given. You can connect any node from the first tree to any node from the second tree with a single edge. The task is to choose the connection that produces the smallest possible diameter of the resulting tree.
Approach 1: Tree Diameter Calculation (O(n + m) time, O(n + m) space)
This approach relies on a key property of trees: the best way to minimize the resulting diameter is to connect the centers of the two trees. Start by computing the diameter of each tree independently using two DFS/BFS passes. First traversal finds the farthest node from any starting node, and the second traversal from that node gives the diameter length.
Once you know the diameter d, the tree's radius is ceil(d / 2). When two trees are merged optimally, the new diameter becomes the maximum of three values: d1, d2, and ceil(d1/2) + ceil(d2/2) + 1. The first two represent the original diameters that might still dominate, while the third represents the path that travels through the newly added edge. This method only requires building adjacency lists and running DFS/BFS traversals. It works naturally with tree and breadth-first search or depth-first search techniques.
Approach 2: Dynamic Programming and Merging Strategy (O(n + m) time, O(n + m) space)
This version computes subtree heights and longest paths using dynamic programming on trees. During traversal, track the two largest child heights for every node to maintain the longest path passing through that node. This gives the diameter of each tree without explicitly performing the classic double BFS trick.
After computing diameters and node heights, derive each tree's effective radius from the DP results. The optimal merge again connects the best center-like nodes, producing the same formula for the final diameter: max(d1, d2, r1 + r2 + 1). This approach is useful when you already maintain DP state on trees or need to extend the solution with additional per-node calculations.
Recommended for interviews: The tree diameter approach using two BFS/DFS passes is the expected solution. It shows you understand tree diameter properties and how centers minimize path lengths. The DP variant demonstrates deeper mastery of graph traversal and tree DP, but most interviewers look for the clean diameter + radius insight.
Approach 1: Approach using Tree Diameter Calculation
This approach involves calculating the diameter of each tree individually. The key observation is that connecting two trees will increase the diameter if the added edge connects the nodes that already are part of their tree's longest path (diameter ends). Therefore, first calculate the diameter of each tree and then consider possible merging nodes to find the minimum resulting diameter.
from collections import deque, defaultdict
def tree_diameter(edges):
if not edges:
return 0
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
def bfs(node):
visited = set()
queue = deque([(node, 0)])
visited.add(node)
farthest_node, max_dist = node, 0
while queue:
current, dist = queue.popleft()
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
if dist + 1 > max_dist:
farthest_node, max_dist = neighbor, dist + 1
return farthest_node, max_dist
far_node, _ = bfs(0)
_, diameter = bfs(far_node)
return diameter
def min_tree_diameter(edges1, edges2):
d1 = tree_diameter(edges1)
d2 = tree_diameter(edges2)
return max((d1 + 1) // 2 + (d2 + 1) // 2 + 1, max(d1, d2))
# Example usage
edges1 = [[0,1],[0,2],[0,3]]
edges2 = [[0,1]]
print(min_tree_diameter(edges1, edges2)) # Output: 3#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;
int bfs(int start, unordered_map<int, vector<int>>& graph) {
queue<pair<int, int>> q;
unordered_map<int, bool> visited;
q.push({start, 0});
visited[start] = true;
int maxDist = 0, node = start;
while (!q.empty()) {
int curr = q.front().first;
int dist = q.front().second;
q.pop();
for (int neighbor : graph[curr]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push({neighbor, dist + 1});
if (dist + 1 > maxDist) {
maxDist = dist + 1;
node = neighbor;
}
}
}
}
return node;
}
int treeDiameter(vector<vector<int>>& edges) {
unordered_map<int, vector<int>> graph;
if (edges.empty()) return 0;
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
int node = bfs(0, graph);
pair<int, int> result = bfs(node, graph);
return result.second;
}
int minTreeDiameter(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
int d1 = treeDiameter(edges1);
int d2 = treeDiameter(edges2);
return max((d1 + 1) / 2 + (d2 + 1) / 2 + 1, max(d1, d2));
}
// Example usage
// int main() {
// vector<vector<int>> edges1 = {{0, 1}, {0, 2}, {0, 3}};
// vector<vector<int>> edges2 = {{0, 1}};
// cout << minTreeDiameter(edges1, edges2) << endl; // Output: 3
// return 0;
// }The function tree_diameter() calculates the diameter of a tree using BFS starting from an arbitrary node, finding the farthest node from it, and then conducting one more BFS from this farthest node to get the diameter. The main function min_tree_diameter() then uses these diameters to compute the smallest possible diameter according to merging strategies while considering the worst-case longest path in the resulting tree.
Time Complexity: O(n + m), where n and m are the number of nodes in each tree respectively as BFS runs in linear time with respect to the number of edges.
Space Complexity: O(n + m) for storing the graph representation.
Approach 2: Approach using Dynamic Programming and Merging Strategy
This approach involves using dynamic programming to calculate subtree information and merge the trees in an optimal manner to achieve a minimum diameter.
import java.util.*;
public class MinDiameter {
private static class Graph {
private final Map<Integer, List<Integer>> adjList = new HashMap<>();
public void addEdge(int u, int v) {
adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
}
public int getDiameter() {
int n = adjList.size();
int node = bfs(0).getKey();
return bfs(node).getValue();
}
private Pair<Integer, Integer> bfs(int start) {
Queue<int[]> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(new int[]{start, 0});
visited.add(start);
int maxDist = 0, node = start;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int currNode = curr[0], currDist = curr[1];
for (int neighbor : adjList.getOrDefault(currNode, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(new int[]{neighbor, currDist + 1});
if (currDist + 1 > maxDist) {
maxDist = currDist + 1;
node = neighbor;
}
}
}
}
return new Pair<>(node, maxDist);
}
}
public static int minTreeDiameter(int[][] edges1, int[][] edges2) {
Graph tree1 = new Graph();
for (int[] edge : edges1) {
tree1.addEdge(edge[0], edge[1]);
}
int d1 = tree1.getDiameter();
Graph tree2 = new Graph();
for (int[] edge : edges2) {
tree2.addEdge(edge[0], edge[1]);
}
int d2 = tree2.getDiameter();
return Math.max((d1 + 1) / 2 + (d2 + 1) / 2 + 1, Math.max(d1, d2));
}
// Example usage
public static void main(String[] args) {
int[][] edges1 = {{0, 1}, {0, 2}, {0, 3}};
int[][] edges2 = {{0, 1}};
System.out.println(minTreeDiameter(edges1, edges2)); // Output: 3
}
}The Graph class constructs an adjacency list and provides a method to calculate the diameter via BFS. The main method minTreeDiameter() uses two graphs to compute diameters and then finds the minimum possible diameter after merging the trees.
Time Complexity: O(n + m) for calculating diameters using BFS.
Space Complexity: O(n + m) due to using adjacency lists for the graphs.
Approach 3: Two DFS Passes
We denote d_1 and d_2 as the diameters of the two trees, respectively. Then, the diameter of the merged tree can be one of the following two cases:
- The diameter of the merged tree is the diameter of one of the original trees, i.e.,
max(d_1, d_2); - The diameter of the merged tree passes through both of the original trees. We calculate the radii of the original two trees as
r_1 = \lceil \frac{d_1}{2} \rceilandr_2 = \lceil \frac{d_2}{2} \rceil, respectively. Then, the diameter of the merged tree isr_1 + r_2 + 1.
We take the maximum of these two cases.
When calculating the diameter of a tree, we can use two DFS passes. First, we arbitrarily select a node and start a DFS from this node to find the farthest node from it, denoted as node a. Then, we start another DFS from node a to find the farthest node from node a, denoted as node b. It can be proven that the path between node a and node b is the diameter of the tree.
The time complexity is O(n + m), and the space complexity is O(n + m), where n and m are the number of nodes in the two trees, respectively.
function minimumDiameterAfterMerge(edges1: number[][], edges2: number[][]): number {
const d1 = treeDiameter(edges1);
const d2 = treeDiameter(edges2);
return Math.max(d1, d2, Math.ceil(d1 / 2) + Math.ceil(d2 / 2) + 1);
}
function treeDiameter(edges: number[][]): number {
const n = edges.length + 1;
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
let [ans, a] = [0, 0];
const dfs = (i: number, fa: number, t: number): void => {
for (const j of g[i]) {
if (j !== fa) {
dfs(j, i, t + 1);
}
}
if (ans < t) {
ans = t;
a = i;
}
};
dfs(0, -1, 0);
dfs(a, -1, 0);
return ans;
}public class Solution {
private List<int>[] g;
private int ans;
private int a;
public int MinimumDiameterAfterMerge(int[][] edges1, int[][] edges2) {
int d1 = TreeDiameter(edges1);
int d2 = TreeDiameter(edges2);
return Math.Max(Math.Max(d1, d2), (d1 + 1) / 2 + (d2 + 1) / 2 + 1);
}
public int TreeDiameter(int[][] edges) {
int n = edges.Length + 1;
g = new List<int>[n];
for (int k = 0; k < n; ++k) {
g[k] = new List<int>();
}
ans = 0;
a = 0;
foreach (var e in edges) {
int a = e[0], b = e[1];
g[a].Add(b);
g[b].Add(a);
}
Dfs(0, -1, 0);
Dfs(a, -1, 0);
return ans;
}
private void Dfs(int i, int fa, int t) {
foreach (int j in g[i]) {
if (j != fa) {
Dfs(j, i, t + 1);
}
}
if (ans < t) {
ans = t;
a = i;
}
}
}func minimumDiameterAfterMerge(edges1 [][]int, edges2 [][]int) int {
d1 := treeDiameter(edges1)
d2 := treeDiameter(edges2)
return max(d1, d2, (d1+1)/2+(d2+1)/2+1)
}
func treeDiameter(edges [][]int) (ans int) {
n := len(edges) + 1
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
a := 0
var dfs func(i, fa, t int)
dfs = func(i, fa, t int) {
for _, j := range g[i] {
if j != fa {
dfs(j, i, t+1)
}
}
if ans < t {
ans = t
a = i
}
}
dfs(0, -1, 0)
dfs(a, -1, 0)
return
}impl Solution {
pub fn minimum_diameter_after_merge(edges1: Vec<Vec<i32>>, edges2: Vec<Vec<i32>>) -> i32 {
let d1 = Self::tree_diameter(&edges1);
let d2 = Self::tree_diameter(&edges2);
d1.max(d2).max((d1 + 1) / 2 + (d2 + 1) / 2 + 1)
}
fn tree_diameter(edges: &Vec<Vec<i32>>) -> i32 {
let n = edges.len() + 1;
let mut g = vec![vec![]; n];
for e in edges {
let a = e[0] as usize;
let b = e[1] as usize;
g[a].push(b);
g[b].push(a);
}
let mut ans = 0;
let mut a = 0;
fn dfs(g: &Vec<Vec<usize>>, i: usize, fa: isize, t: i32, ans: &mut i32, a: &mut usize) {
for &j in &g[i] {
if j as isize != fa {
dfs(g, j, i as isize, t + 1, ans, a);
}
}
if *ans < t {
*ans = t;
*a = i;
}
}
dfs(&g, 0, -1, 0, &mut ans, &mut a);
dfs(&g, a, -1, 0, &mut ans, &mut a);
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach using Tree Diameter Calculation | Time Complexity: O(n + m), where n and m are the number of nodes in each tree respectively as BFS runs in linear time with respect to the number of edges. |
| Approach using Dynamic Programming and Merging Strategy | Time Complexity: O(n + m) for calculating diameters using BFS. |
| Two DFS Passes | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Tree Diameter Calculation (DFS/BFS) | O(n + m) | O(n + m) | Best general solution. Simple two-pass traversal per tree. |
| Tree DP with Height Tracking | O(n + m) | O(n + m) | Useful when already performing dynamic programming on tree structures. |
Frequently asked questions
Is Find Minimum Diameter After Merging Two Trees easy or hard?
The problem is classified as Hard because it requires understanding tree diameter properties and recognizing that connecting tree centers minimizes the merged diameter. The implementation itself is manageable once the diameter and radius relationship is clear.
How to solve Find Minimum Diameter After Merging Two Trees in O(n)?
Build adjacency lists for both trees and compute each diameter using two BFS or DFS passes. Convert the diameters into radii using ceil(d/2). The final answer is max(d1, d2, r1 + r2 + 1), which represents the worst possible longest path after merging through optimal center nodes.
Find Minimum Diameter After Merging Two Trees Python or Java solution?
Python and C++ implementations typically use the two-pass BFS/DFS diameter technique with adjacency lists. Java solutions often implement a tree dynamic programming approach that tracks subtree heights and longest paths before applying the merge formula.
What is the best approach for Find Minimum Diameter After Merging Two Trees?
The best approach computes the diameter of each tree using two BFS or DFS traversals. After finding diameters d1 and d2, compute their radii as ceil(d/2). The minimum possible merged diameter is max(d1, d2, ceil(d1/2) + ceil(d2/2) + 1). This works because connecting the centers of the trees minimizes the longest path.
What data structure is used in Find Minimum Diameter After Merging Two Trees?
The core data structure is an adjacency list representing the tree as a graph. Traversal is performed using BFS queues or DFS recursion stacks. Additional variables track farthest nodes and distances to compute the diameter.
What is the time complexity of Find Minimum Diameter After Merging Two Trees?
The optimal solution runs in O(n + m) time where n and m are the number of nodes in the two trees. Each tree requires two BFS or DFS traversals to compute its diameter. Space complexity is also O(n + m) for adjacency lists and traversal structures.
Is Find Minimum Diameter After Merging Two Trees asked at Google, Amazon, or Meta?
Tree diameter and tree merging problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations often test knowledge of tree centers, longest path computation, and BFS/DFS traversal strategies.