Diameter of an Undirected Tree

Problem Statement

You are given an undirected, unweighted tree consisting of n nodes labeled from 0 to n - 1. The tree is represented by an array edges of length n - 1, where each edges[i] = [u, v] indicates an undirected edge between node u and node v.

The diameter of a tree is defined as the number of edges on the longest simple path between any two nodes in the tree.

Write a function that returns the diameter of the tree.

Function Signature

def tree_diameter(n: int, edges: list[list[int]]) -> int:
    pass

Input & Output Format

• Input:
  • An integer n, the number of nodes.
  • A 2D list of integers edges, where edges[i] contains two integers u and v representing an edge.
• Output:
  • An integer representing the length (number of edges) of the longest path.

Constraints

• 1 <= n <= 10^5
• edges.length == n - 1
• 0 <= edges[i][0], edges[i][1] < n
• edges[i][0] != edges[i][1]
• The given edges are guaranteed to form a valid, connected tree.

Examples

Example 1

Input: n = 4, edges = [[0, 1], [1, 2], [2, 3]]
Output: 3
Explanation: The longest path connects node 0 to node 3 (0 - 1 - 2 - 3), which consists of 3 edges.

Example 2

Input: n = 6, edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5]]
Output: 4
Explanation: One longest path is 3 - 1 - 0 - 2 - 5, which consists of 4 edges.

Edge Cases

• n = 1 with edges = []: A single node has a diameter of 0.
• Linear chain graph: The diameter is n - 1; beware of recursion limit if using recursion in Python.
• Star graph: A central node connected to n - 1 leaves has a diameter of 2 (for n >= 3).