Katkat
Back

Compute the Diameter of an Undirected Tree

QualcommSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Compute the diameter of a large undirected tree, measured by the number of edges on its longest simple path. The exercise tests adjacency construction, linear-time tree traversal, endpoint reasoning, recursion-depth awareness, and edge cases such as a single-node tree.

Compute the Diameter of an Undirected Tree

You are given an undirected tree with nodes numbered from 0 through n - 1. The diameter is the number of edges on the longest simple path between any two nodes.

Return the tree's diameter.

Function Signature

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

Input and Output

  • Each element of edges is [u, v] and represents one undirected edge.
  • Return the maximum number of edges on any simple path.

Constraints

  • 1 <= n <= 100_000
  • len(edges) == n - 1
  • 0 <= u, v < n and u != v
  • The input graph is connected and contains no cycle.

Examples

Input: n = 5, edges = [[0, 1], [1, 2], [1, 3], [3, 4]]
Output: 3

Input: n = 1, edges = []
Output: 0