Domain 2MediumMEDIUM

Tree Diameter

Find tree diameter using two BFS traversals from an arbitrary node to find endpoints of the longest path.

Domain: medium•Updated: 2026-09-11
#BFS#Tree Diameter#O(N) Time Complexity#O(N) Space Complexity

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 KK edges, there are implicitly K+1K+1 nodes labeled from 0 to edges.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 edges list: Represents a single node with no edges; diameter should be 0.
    • Single edge ([[u,v]]): Diameter is 1.

Intuition

A brute-force approach would calculate the distance between every pair of nodes using BFS or DFS, resulting in O(N2)O(N^2) time complexity where NN is the number of edges/nodes. Given constraints up to 10410^4, this might pass but isn’t optimal for a senior role; we aim for linear time O(N)O(N).

The key insight relies on tree properties:

  1. 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.
  2. 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

  1. Graph Construction: Convert the edge list into an adjacency list (dictionary mapping nodes to lists of neighbors) for efficient traversal (O(1)O(1) neighbor access). Handle undirected nature by adding edges both ways.
  2. 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).
  3. Second Traversal (BFS): Run another BFS starting specifically from farthest_node. The maximum distance encountered in this second traversal is our answer.
  4. Return: Return the max distance found in step 3.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the number of edges (nodes = N+1N+1). 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: O(N)O(N). We store an adjacency list for the graph (2×E2 \times E 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 edges and returns 0, handling a single-node tree correctly.
  • Single Node Tree: Covered by the empty input check (since N=1N=1 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 (10410^4): 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).