Show problems as
Classic problem #1245MediumTreeDepth-First SearchBreadth-First SearchGraph TheoryTopological SortDP on Trees

Tree Diameter

Real-world version: The Longest Walk in a Pipe Network
Tracked in this browser only
Read Tree Diameter on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A network of junctions is joined by the pipes pipes, where pipes[i] = [a, b] is a two-way pipe between junction a and junction b. The network holds one more junction than it has pipes, and the junctions are numbered from 0 upwards. Every junction is reachable from every other, and there is no loop anywhere.

Return the greatest number of pipes on any walk between two junctions that never uses a pipe twice.

Examples

Example 1

Input
pipes = [[0, 1], [1, 2], [2, 3], [3, 4], [2, 5]]
Output
4

Six junctions. The walk from 0 through 1, 2 and 3 to 4 uses four pipes, and so does the walk from 0 to 5 by way of 1 and 2 plus one more. Nothing longer exists, since junction 2 is where the two ends part company.

Example 2

Input
pipes = []
Output
0

No pipes means a single junction, and a walk that goes nowhere uses none.

Example 3

Input
pipes = [[0, 1], [0, 2], [0, 3], [0, 4]]
Output
2

Every junction hangs straight off junction 0, so the longest walk goes from one of them through 0 to another, using two pipes.

Constraints

  • 0 <= pipes.length <= 9999
  • pipes[i].length == 2
  • 0 <= pipes[i][j] <= pipes.length
  • The two ends of a pipe are different junctions.
  • The pipes reach every junction and hold no loop.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def tree_diameter(pipes: list[list[int]]) -> int:
Java
public int treeDiameter(int[][] pipes)

More on the same topics