Return nodes on a tree diameter path

Q: Return nodes on a tree diameter path

This question evaluates understanding of graph algorithms and tree properties, specifically the ability to identify and reconstruct a longest simple path (diameter) in an undirected tree.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

You are given an undirected tree with n nodes labeled 0..n-1 (connected, no cycles). The diameter of a tree is the longest simple path between any two nodes.

Return the nodes (in order) along one diameter path (if multiple diameter paths exist, returning any one of them is acceptable).

Input

Integer n ( 2 <= n <= 2 * 10^5 )
List of n - 1 edges edges , where each edge is a pair [u, v] with 0 <= u, v < n

Output

A list/array path containing the node labels along a longest path (diameter), from one endpoint to the other.

Constraints

The input graph is guaranteed to be a tree.

Example

Input:

n = 6
edges = [[0,1],[1,2],[1,3],[3,4],[4,5]]

One valid output:

[2,1,3,4,5]

Explanation: the longest path has length 4 edges, from node 2 to node 5.