Problem Breakdown
We are given an undirected tree represented as a list of bidirectional edges [[u, v], ...]. The goal is to find the diameter of this tree—the number of edges in its longest path between any two nodes.
Key constraints and details:
- Input: A list of edge pairs defining connections. If there are edges, there are implicitly nodes labeled from
0toedges.length. - Output: An integer representing the maximum distance (edge count) between any two nodes in the tree.
- Implicit Constraints: The input is guaranteed to form a valid undirected tree (connected, acyclic). Node labels are non-negative integers within bounds.
- Edge Cases:
- Empty
edgeslist: Represents a single node with no edges; diameter should be 0. - Single edge (
[[u,v]]): Diameter is 1.
- Empty
Intuition
A brute-force approach would calculate the distance between every pair of nodes using BFS or DFS, resulting in time complexity where is the number of edges/nodes. Given constraints up to , this might pass but isn’t optimal for a senior role; we aim for linear time .
The key insight relies on tree properties:
- In any tree, if you start from an arbitrary node and traverse as far as possible (BFS/DFS), the furthest reachable node is guaranteed to be one of the endpoints of the diameter.
- Once we identify that endpoint, running a traversal again starting specifically from it will lead us directly to the other endpoint of the longest path in the tree.
Thus, two traversals are sufficient: find the farthest node from an arbitrary start, then find the farthest node from that result. The distance found in the second step is the diameter.
Approach
- Graph Construction: Convert the edge list into an adjacency list (dictionary mapping nodes to lists of neighbors) for efficient traversal ( neighbor access). Handle undirected nature by adding edges both ways.
- First Traversal (BFS): Start a BFS from node
0(since it’s guaranteed to exist if there are any edges, or we handle the empty case separately). Track visited nodes and distances. Identify the node with the maximum distance reached (farthest_node). - Second Traversal (BFS): Run another BFS starting specifically from
farthest_node. The maximum distance encountered in this second traversal is our answer. - Return: Return the max distance found in step 3.
Complexity Analysis
- Time Complexity: , where is the number of edges (nodes = ). We iterate through all nodes and edges exactly twice during BFS operations. Building the adjacency list takes one pass over
edges. Total work is linear relative to input size. - Space Complexity: . We store an adjacency list for the graph ( entries), plus a queue/visited set per BFS traversal, which scales with the number of nodes.
Solution
from collections import deque, defaultdict
from typing import List
class Solution:
def treeDiameter(self, edges: List[List[int]]) -> int:
# Edge case: No edges means a single node (0 diameter)
if not edges:
return 0
# Build adjacency list for undirected graph
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
def bfs(start_node):
"""Returns (farthest_node_from_start, distance_to_it)"""
queue = deque([(start_node, 0)])
visited = {start_node}
farthest_node = start_node
max_dist = -1
while queue:
curr, dist = queue.popleft()
# Update if we found a longer path so far
if dist > max_dist:
max_dist = dist
farthest_node = curr
for neighbor in adj[curr]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return (farthest_node, max_dist)
# First BFS from arbitrary node '0' to find one endpoint of the diameter.
# Node 0 is guaranteed to exist and be part of the connected component given constraints.
_, farthest_from_0 = bfs(0)
# Second BFS from that endpoint finds the actual diameter length
_, diameter = bfs(farthest_from_0)
return diameter
Edge Cases Handled
- Empty Input: Explicitly checks
if not edgesand returns 0, handling a single-node tree correctly. - Single Node Tree: Covered by the empty input check (since implies 0 edges). If there were nodes but no connections in other contexts, this logic holds for connected trees only as per constraints.
- Large Inputs (): The linear BFS approach ensures memory and time usage remain within limits without recursion depth issues (using iterative queue instead of recursive DFS prevents stack overflow risks on deep trees).