How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

Return nodes on a tree diameter path | Citadel Coding Question

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.

Return nodes on a tree diameter path

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## 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`.

Quick Answer: 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.

You are given an undirected tree with n nodes labeled 0 to n - 1. A tree diameter is a longest simple path between any two nodes in the tree. Return the node labels, in order, along one diameter path. If multiple diameter paths exist, returning any one valid diameter path is acceptable.

Constraints

2 <= n <= 2 * 10^5
len(edges) == n - 1
0 <= u, v < n for every edge [u, v]
The input graph is guaranteed to be connected and acyclic

Examples

Input: (6, [[0,1],[1,2],[1,3],[3,4],[4,5]])

Expected Output: [2,1,3,4,5]

Explanation: The path from node 2 to node 5 has 4 edges, which is a maximum-length path in this tree.

Input: (2, [[0,1]])

Expected Output: [0,1]

Explanation: With only two nodes, the single edge is the diameter path.

Input: (5, [[0,1],[1,2],[2,3],[3,4]])

Expected Output: [0,1,2,3,4]

Explanation: The tree is already a straight chain, so the entire chain is the diameter path.

Input: (5, [[0,1],[0,2],[0,3],[0,4]])

Expected Output: [3,0,4]

Explanation: Any path between two leaves has length 2, which is the diameter length. The shown path is one valid diameter.

Input: (8, [[0,1],[1,2],[2,3],[1,4],[4,5],[5,6],[6,7]])

Expected Output: [3,2,1,4,5,6,7]

Explanation: The longest path goes from node 3 to node 7 and contains 6 edges.

Hints

In a tree, if you run BFS or DFS from any node, one of the farthest nodes you find is an endpoint of a diameter.
After finding one diameter endpoint, run another BFS or DFS from it while storing parents so you can reconstruct the path to the farthest node.

Quick Overview

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.