Compute the Diameter of an Undirected Tree

Quick Overview

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.

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

Overview: 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.

Approach

The reference runs two breadth-first searches (the standard double sweep), which is linear in the size of the tree.

First build an adjacency structure, adding every edge in both directions -- the input is undirected, and storing only u -> v silently turns the tree into a directed forest that answers a different question.

Then:

Run a BFS from node 0 (any node will do) and keep the node a at maximum distance from it.
Run a second BFS from a. The maximum distance reached in that second search is the diameter.

Why step 1 is enough to find a genuine endpoint: let P be some longest path in the tree. If the search's start node lies on P, the farthest node from it must be one of P's two ends, since walking further along P in the longer direction is always at least as far as leaving P. If the start node does not lie on P, the path from it to P first touches P at a unique node m (unique because a tree has exactly one path between any two nodes); the farthest node from the start is then whichever end of P is farther from m, because any alternative branch could be spliced into P to produce a strictly longer path, contradicting that P was longest. Either way a is an endpoint of a longest path, so the second BFS measures a full diameter.

Note what step 1 alone does not give you. The distance from node 0 to its farthest node is the eccentricity of node 0, which is generally smaller than the diameter -- on a star it is 1 while the diameter is 2. The second sweep is what turns an arbitrary start into an answer about the whole tree.

The implementation keeps both sweeps in a single loop that runs twice, re-seeding source with the farthest node found. Both sweeps use an explicit array-backed queue and a distance array initialised to -1 (which doubles as the visited mark), so nothing recurses: a path graph on 100000 nodes would otherwise overflow the Python recursion limit and the Java call stack. The n <= 1 guard returns 0 up front, which also keeps the empty edges list from ever being indexed.

Distances only ever grow to n - 1 <= 99999, so int is the correct width in Java and C++ and no value comes near the JavaScript safe-integer range. The Java reference flattens the adjacency into CSR-style head/adjacency arrays to avoid allocating 100000 boxed lists; Python, JavaScript and C++ use nested lists or vectors directly.

There is an equally linear alternative: root the tree anywhere, compute every node's height with an iterative post-order pass, and at each node combine its two deepest child heights as top1 + top2. The diameter is the maximum of that quantity over all nodes, because a longest path bends at exactly one node and that node contributes its own top1 + top2. The maximisation is the whole algorithm -- evaluating top1 + top2 only at the root computes the longest path through the root, which is a different and usually smaller number whenever the root sits off the longest path. Test case 4 is the minimal example: n = 6, edges = [[0,1],[1,2],[2,3],[1,4],[4,5]], where the diameter is 4 but the longest path through node 0 is only 3.

Time complexity:

O(n) -- building the adjacency structure touches each of the n - 1 edges once, and each of the two breadth-first sweeps dequeues every node at most once and scans each adjacency entry at most once, so the total work is linear in the number of nodes and edges.

Space complexity:

O(n) -- the adjacency structure holds 2 * (n - 1) entries, and the distance array and the queue are each of length n. The input is read but never copied wholesale or mutated.