FastPrep
Problem · Graph

Diameter of an Acyclic Undirected Graph

Learn this problem
● MediumSalesforce logoSalesforceFULLTIMEONSITE INTERVIEW
See Salesforce hiring insights

Problem statement

You are given a connected, undirected, acyclic graph, so the graph is a tree. The tree has n vertices labeled from 0 to n - 1 and n - 1 edges.

The diameter of the tree is the maximum number of edges on any simple path between two vertices.

Implement treeDiameter(n, edges) and return the tree's diameter.

  • edges[i] = [u, v] denotes an undirected edge between vertices u and v.
  • A tree with one vertex has diameter 0.

Function

treeDiameter(n: int, edges: int[][]) → int

Examples

Example 1

n = 4edges = [[0,1],[1,2],[1,3]]return = 2

A longest path is 2 - 1 - 3, which contains two edges.

Example 2

n = 1edges = []return = 0

The single-vertex tree has no edges.

Constraints

  • 1 <= n <= 100000
  • edges.length = n - 1
  • 0 <= u, v < n
  • The input graph is connected and acyclic.

More Salesforce problems

drafts saved locally
public int treeDiameter(int n, int[][] edges) {
  // Write your code here.
}
n4
edges[[0,1],[1,2],[1,3]]
expected2
checking account