Maximum Tree Diameter — Problem Statement & Solution Guide
Problem Description
Given a connected, undirected tree with N nodes, find the maximum diameter, defined as the longest simple path between any two nodes. The input is a list of edges, where each edge is a list of two nodes.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Tree Diameter"
WHY DOES IT MATTER?
Understanding tree diameter is fundamental for problems involving network latency, longest communication chains, and hierarchical data structures. The pattern teaches candidates how to exploit acyclic properties and transform a global optimization problem into two local traversals, a technique that recurs in many graph‑theoretic challenges.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that a single BFS/DFS can locate one endpoint of the diameter, turning an O(N^2) all‑pairs problem into two linear passes. Maintaining only two longest child depths during a post‑order DP also achieves the same result without extra traversals.
REAL-WORLD CONNECTION
Consider a distributed file system where servers form a tree topology. The diameter corresponds to the worst‑case replication delay between two farthest servers; minimizing this delay is crucial for consistency guarantees and load balancing.
When coding, start with a simple recursive DFS that returns the longest downward path; use a mutable reference or global variable to update the maximum diameter on the fly. This avoids storing large auxiliary arrays and keeps the implementation clean under time pressure.
COMPLEXITY AT A GLANCE
O(N)O(N)Core Theory — Why This Approach?
The diameter of a tree is the length (in edges or weighted sum) of the longest simple path between any two vertices. In an unrooted tree, this path always lies between two leaf nodes, and it can be discovered using two depth‑first searches (DFS) or breadth‑first searches (BFS). The first traversal starts from an arbitrary node and finds the farthest node X; the second traversal starts from X and finds the farthest node Y, and the distance between X and Y is the tree diameter. This works because any longest path must have one endpoint that is the farthest from any starting point, a property derived from the tree’s acyclic nature and the triangle inequality on paths. Naïve methods—such as enumerating all pairs of nodes and computing their distances—require O(N^2) time, which is infeasible for N up to 10^5 or higher. The optimal paradigm leverages the fact that a tree has a unique simple path between any two nodes, allowing linear‑time exploration with DP‑style propagation of depths from leaves upward, or the classic two‑BFS/DFS trick, both achieving O(N) time and O(N) space.
Dynamic programming on trees formalizes this intuition: for each node we can store the longest and second‑longest downward paths among its children. While performing a post‑order DFS, we update a global maximum with the sum of the two longest child depths plus the edges to the current node, which captures any diameter that passes through that node. This DP approach also runs in linear time and is particularly handy when the tree is rooted or when additional constraints (e.g., weighted edges, node values) are introduced. The key insight is that the diameter either lies entirely within a subtree or passes through the current node, and both cases are covered by maintaining just the top two depths.
Interview Questions on This Problem
Q1How would you compute the diameter of a weighted tree where each edge has a positive length?
Perform two BFS/DFS traversals using a priority queue or recursion that accumulates distances: start from any node, find the farthest node X (by total weight), then start from X to find the farthest node Y; the accumulated distance to Y is the weighted diameter.
Q2Can you modify the algorithm to also return the actual nodes that constitute the diameter path?
Yes. During the second BFS/DFS, keep a parent pointer for each visited node. Once the farthest node Y is identified, backtrack using the parent map to reconstruct the path from Y to the start node X.
Q3Why does the two‑DFS method guarantee the longest path in a tree, but not necessarily in a general graph?
A tree has exactly one simple path between any two vertices and no cycles, so the farthest node from any start must be an endpoint of a diameter. In a general graph, multiple paths and cycles can produce longer routes that are not captured by a single farthest‑node search.
Examples
Input
[[1,2],[1,3],[1,4],[1,5],[1,6],[2,3],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6],[4,5],[4,6],[5,6]]
Output
5
Explanation: Step-by-step: Given the input graph, we start from node 1 and perform a BFS traversal. The longest path is 1 -> 2 -> 3 -> 4 -> 5 with a length of 5.
Input
[[1,2],[1,3],[1,4],[1,5],[1,6],[2,3],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6],[4,5],[4,6],[5,6],[6,7]]
Output
5
Explanation: Step-by-step: Given the input graph, we start from node 1 and perform a BFS traversal. The longest path is 1 -> 2 -> 3 -> 4 -> 5 -> 6 with a length of 5.
Constraints
- The tree is connected and undirected.
- The tree has N nodes, where 2 <= N <= 1000.
- Each node has a unique value between 1 and 1000.
- The tree edges are given as a list of pairs (u, v), where u and v are node values.
Optimal Approach & Strategy
Run two linear‑time DFS/BFS traversals: first to find an extreme node, second to compute the farthest distance from that node, yielding the diameter in O(N) time.
Brute Force Approach
Enumerate every pair of nodes, compute the unique path length between them, and keep the maximum; this requires O(N^2) time. It quickly becomes impractical for N > 10^4.
Verified Code Solutions
function solution(edges) {
if (edges.length === 0 || edges.length === 1) return 1;
const graph = {};
for (const [u, v] of edges) {
if (!graph[u]) graph[u] = [];
if (!graph[v]) graph[v] = [];
graph[u].push(v);
graph[v].push(u);
}
let maxDiameter = 0;
function bfs(node, parent) {
const queue = [[node, 0]];
const visited = new Set([node]);
let maxDistance = 0;
while (queue.length > 0) {
const [currNode, distance] = queue.shift();
maxDistance = Math.max(maxDistance, distance);
for (const neighbor of graph[currNode]) {
if (neighbor !== parent && !visited.has(neighbor)) {
queue.push([neighbor, distance + 1]);
visited.add(neighbor);
}
}
}
return maxDistance;
}
for (const node in graph) {
maxDiameter = Math.max(maxDiameter, bfs(node, null));
}
return maxDiameter;
}class Solution {
public:
int solution(vector<vector<int>>& edges) {
if (edges.size() == 0 || edges.size() == 1) return 1;
unordered_map<int, vector<int>> graph;
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
if (graph.find(u) == graph.end()) graph[u] = {};
if (graph.find(v) == graph.end()) graph[v] = {};
graph[u].push_back(v);
graph[v].push_back(u);
}
int maxDiameter = 0;
for (auto& node : graph) {
maxDiameter = max(maxDiameter, bfs(node.first, nullptr));
}
return maxDiameter;
}
private:
int bfs(int node, int parent) {
queue<int[]> q;
q.push({node, 0});
unordered_set<int> visited;
visited.insert(node);
int maxDistance = 0;
while (!q.empty()) {
int* curr = q.front();
maxDistance = max(maxDistance, curr[1]);
for (int neighbor : graph[node]) {
if (neighbor != parent && visited.find(neighbor) == visited.end()) {
q.push({neighbor, curr[1] + 1});
visited.insert(neighbor);
}
}
q.pop();
}
return maxDistance;
}
}class Solution {
public int solution(int[][] edges) {
if (edges.length == 0 || edges.length == 1) return 1;
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
if (!graph.containsKey(u)) graph.put(u, new ArrayList<>());
if (!graph.containsKey(v)) graph.put(v, new ArrayList<>());
graph.get(u).add(v);
graph.get(v).add(u);
}
int maxDiameter = 0;
for (int node : graph.keySet()) {
maxDiameter = Math.max(maxDiameter, bfs(node, null));
}
return maxDiameter;
}
private int bfs(int node, int parent) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {node, 0});
Set<Integer> visited = new HashSet<>();
visited.add(node);
int maxDistance = 0;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
maxDistance = Math.max(maxDistance, curr[1]);
for (int neighbor : graph.get(curr[0])) {
if (neighbor != parent && !visited.contains(neighbor)) {
queue.offer(new int[] {neighbor, curr[1] + 1});
visited.add(neighbor);
}
}
}
return maxDistance;
}
}def solution(edges):
if not edges or len(edges) == 1:
return 1
graph = {}
for u, v in edges:
if u not in graph:
graph[u] = []
if v not in graph:
graph[v] = []
graph[u].append(v)
graph[v].append(u)
max_diameter = 0
def bfs(node, parent):
queue = [[node, 0]]
visited = set([node])
max_distance = 0
while queue:
curr_node, distance = queue.pop(0)
max_distance = max(max_distance, distance)
for neighbor in graph[curr_node]:
if neighbor != parent and neighbor not in visited:
queue.append([neighbor, distance + 1])
visited.add(neighbor)
return max_distance
for node in graph:
max_diameter = max(max_diameter, bfs(node, None))
return max_diameterfunction solution(edges) {
if (edges.length === 0 || edges.length === 1) return 1;
const graph = {};
for (const [u, v] of edges) {
if (!graph[u]) graph[u] = [];
if (!graph[v]) graph[v] = [];
graph[u].push(v);
graph[v].push(u);
}
let maxDiameter = 0;
function bfs(node, parent) {
const queue = [[node, 0]];
const visited = new Set([node]);
let maxDistance = 0;
while (queue.length > 0) {
const [currNode, distance] = queue.shift();
maxDistance = Math.max(maxDistance, distance);
for (const neighbor of graph[currNode]) {
if (neighbor !== parent && !visited.has(neighbor)) {
queue.push([neighbor, distance + 1]);
visited.add(neighbor);
}
}
}
return maxDistance;
}
for (const node in graph) {
maxDiameter = Math.max(maxDiameter, bfs(node, null));
}
return maxDiameter;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.