Compute the Diameter of an Undirected Tree
Company: Qualcomm
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Compute the Diameter of an Undirected Tree
You are given an undirected tree with nodes numbered from `0` through `n - 1`. The **diameter** is the number of edges on the longest simple path between any two nodes.
Return the tree's diameter.
## Function Signature
```python
def tree_diameter(n: int, edges: list[list[int]]) -> int:
...
```
## Input and Output
- Each element of `edges` is `[u, v]` and represents one undirected edge.
- Return the maximum number of edges on any simple path.
## Constraints
- `1 <= n <= 100_000`
- `len(edges) == n - 1`
- `0 <= u, v < n` and `u != v`
- The input graph is connected and contains no cycle.
## Examples
```text
Input: n = 5, edges = [[0, 1], [1, 2], [1, 3], [3, 4]]
Output: 3
```
```text
Input: n = 1, edges = []
Output: 0
```
Quick Answer: Compute the diameter of a large undirected tree, measured by the number of edges on its longest simple path. The exercise tests adjacency construction, linear-time tree traversal, endpoint reasoning, recursion-depth awareness, and edge cases such as a single-node tree.
You are given an undirected tree whose nodes are numbered `0` through `n - 1`.
A **simple path** is a path that visits no node twice. The **diameter** of the tree is the number of **edges** on the longest simple path between any two nodes.
Return the tree's diameter.
## Function
```
tree_diameter(n, edges)
```
## Input
- `n` is the number of nodes.
- `edges` is a list of pairs. Each element is `[u, v]` and represents one **undirected** edge between node `u` and node `v`. An edge may be written `[u, v]` or `[v, u]`, and the pairs may appear in any order.
## Output
Return a single integer: the maximum number of edges on any simple path in the tree.
The answer counts **edges**, not nodes, so a path through `k` nodes contributes `k - 1`. A tree with a single node has no edges and its diameter is `0`.
The maximum is taken over **every** pair of nodes. Node `0` is not privileged in any way: a longest path may lie entirely inside one part of the tree and need not touch node `0`, and it need not touch the highest-degree node either.
The answer is one integer, so there is nothing to order or tie-break. Several different paths may share the maximum length; the diameter is that shared length, and which of those paths achieves it never matters.
## Constraints
- `1 <= n <= 100000`
- `len(edges) == n - 1`
- `0 <= u, v < n` and `u != v` for every edge
- The input graph is connected and contains no cycle, so it is always a tree.
- Every value in the input is a node index of at most `n - 1 <= 99999`, and the answer is at most `n - 1 <= 99999`. Nothing in this problem approaches a 32-bit integer limit or a JavaScript precision limit, so `int` is the correct width in Java and C++.
- Do not mutate `edges`.
## Examples
**Example 1**
```
n = 5
edges = [[0, 1], [1, 2], [1, 3], [3, 4]]
output = 3
```
Node `1` is joined to `0`, `2` and `3`, and node `3` is also joined to `4`. The path `2 - 1 - 3 - 4` uses 3 edges, and so does `0 - 1 - 3 - 4`. No simple path is longer, so the diameter is `3`.
**Example 2**
```
n = 1
edges = []
output = 0
```
A single node has no edges, so the longest simple path has length `0`.
Constraints
- 1 <= n <= 100000
- len(edges) == n - 1
- 0 <= u, v < n and u != v for every edge [u, v]
- The input graph is connected and contains no cycle, so it is always a tree.
- Edges are undirected: [u, v] and [v, u] describe the same edge, and the pairs may be listed in any order.
- The maximum runs over every pair of nodes; a longest path need not pass through node 0 or through the highest-degree node.
- Every input value is a node index of at most n - 1 <= 99999 and the answer is at most n - 1 <= 99999, so no quantity approaches a 32-bit integer limit or a JavaScript precision limit; `int` is the correct width in Java and C++.
- `edges` must not be mutated.
Examples
Input: (5, [[0,1],[1,2],[1,3],[3,4]])
Expected Output: 3
Explanation: Source example 1, carried over verbatim. Node 1 joins 0, 2 and 3, and node 3 also holds 4. The longest simple paths are 2-1-3-4 and 0-1-3-4, both 3 edges, so the diameter is 3.
Input: (1, [])
Expected Output: 0
Explanation: Source example 2, carried over verbatim. A single node has no edges, so the longest simple path has 0 edges.
Hints
- The diameter belongs to the whole tree, not to any one node. How far the deepest node sits from node `0` answers a different question -- try that idea on a tree where node `0` is a leaf dangling off the middle of a long chain.
- If you root the tree and compute each node's height, remember that the longest path bends at some node. That node is rarely the root, so whatever quantity you form at a node has to be maximised over **all** nodes before you report it.
- A different route: suppose you already knew one endpoint of some longest path. Finding the other endpoint is then a single traversal. So the question becomes how to get hold of one genuine endpoint cheaply -- and one traversal from an arbitrary start is enough to land on one.
- Whatever traversal you choose, keep it iterative with an explicit queue or stack. `n` reaches 100000 and a tree that shape can be a single chain, deep enough to exhaust the recursion limit in Python and the call stack in Java. Also remember to add every edge to the adjacency structure in **both** directions.