Katkat
Back

Return nodes on a tree diameter path

CitadelSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to perform a two-pass Breadth-First Search (BFS) or Depth-First Search (DFS) on an undirected tree to find the longest path and reconstruct the sequence of nodes that form it.

Problem Statement

Given an undirected tree represented as an adjacency list with n nodes (labeled 0 to n-1), return any path of nodes that represents the diameter of the tree. The diameter is defined as the longest simple path between any two nodes in the tree.

Function Signature

def find_diameter_path(n: int, edges: List[List[int]]) -> List[int]:

Constraints

  • n is between 2 and 10,000.
  • edges contains n-1 connections forming a valid tree structure.

Examples

Example 1:

  • Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
  • Output: [0, 1, 2, 3, 4] (or [4, 3, 2, 1, 0])
  • Explanation: This is a linear tree; the longest path spans all nodes.

Example 2:

  • Input: n = 4, edges = [[0, 1], [1, 2], [1, 3]]
  • Output: [0, 1, 2] or [0, 1, 3] or [2, 1, 3]
  • Explanation: All these paths have length 2, which is the diameter.

Edge Cases

  • A tree with only two nodes.
  • A star-shaped tree where one central node is connected to all others.

Hints

Hint 1

Recall that the diameter of a tree can be found by running two BFS traversals: the first starting from an arbitrary node to find the furthest node 'u', and the second starting from 'u' to find the furthest node 'v'.

Hint 2

To reconstruct the path, you need to store the parent of each node during the second BFS traversal to backtrack from 'v' to 'u'.

Hint 3

If you use DFS, you can pass the path taken so far through the recursive calls and update a global 'longest path' variable whenever a leaf node is reached.

Follow-up questions

  • How would your approach change if the tree edges had positive weights instead of being unweighted?
  • Can you find the diameter if the tree is represented as a list of parent pointers instead of an adjacency list?
  • What is the time and space complexity of your solution, and can it be optimized if we only need the length of the diameter rather than the path itself?