# Diameter of a Tree

## Problem Description
A **tree** is defined as an unweighted undirected graph.

$$
T = (V, E)
$$

The **diameter** of the tree is defined as the longest distance between all pairs of nodes.
$$
\text{diameter}(T)=max_{(u, v)\in E} \text{ }d(u, v)
$$

Note that distance between any pair of node is **unique**.

The goal is to find the diameter inside a tree.

For example, in the following tree, the diameter = 3
(Path: 1, 2, 4, 5)


## Algorithm
This problem can be solved by running two times of **BFS**.

let s be an arbitrary vertex
perform BFS on s and let u be the furthest vertex from s
perform BFS on u and let v be the furthest vertex from u
return d(u, v)

## Proof
Let `u` and `v` be the endpoints of diameter.

If we perform BFS from `u`, we are bound to find `v` as the furthest vertex. (otherwise, `(u,v)` won't be the diameter, as we can find a longer path than `(u, v)`)

So it suffices to prove that **in the first BFS, we will find one endpoint of the diameter**.

Let `w` be the furthest node from s (found in the first BFS). We will prove by **contradiction**, thus assume `w != u` and `w != v`.

consider the trees in the following cases:
+ `s` on the diameter
+ `s` NOT on the diameter
+ path of `s` to `w` intersects with the diameter
+ path of `s` to `w` does NOT intersect with the diameter

### Case 1: `s` on the diameter


WLOG, let `d(s, v) >= d(s, u)`. Since `w` is furthest from `s`, then

d(u, w) = d(u, s) + d(s, w) > d(u, s) + d(s, v) = d(u, v)

A contradiction occurs, as path from `u` to `w` is longer than `u` to `v`. Therefore, `w` must be `u` or `v` in this case.

We can conclude an important lemma from case 1.
#### Lemma
> **If we perform BFS on any node which is on the diamter, we will find an endpoint of the diameter as the furthest node from the starting node.**


### Case 2: `s` NOT on the diameter

#### Case 2-1: `s` to `w` intersects with the diameter

Let `i` be the intersection node.


Since `i` is on the diameter, then by lemma, the node furthest from `i` must be `u` or `v`.

Thus the furthest node from `s` must be `u` or `v`.

#### Case 2-2: `s` to `w` does NOT intersect with the diameter

Let `i` and `j` be the nodes on `s->w` and `u->v`, respectively, and they connects both path.


WLOG, assume `d(j, v) > d(j, u)`.
Since `w` is farthest from `s`, then `d(i, w) > d(i, v)`.


Furthermore, we can deduce that `d(w, j) > d(j, v)`.


However, `j` is on the diameter, by lemma, the furthest node from `j` must be `v`. Thus a contradiction occurs.

###### tags: `Algorithm` `BFS`