---
# System prepended metadata

title: Diameter of a Tree
tags: [BFS, Algorithm]

---

# 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)

![](https://i.imgur.com/jli2zSa.png)

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

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

![](https://i.imgur.com/coUI3NH.png)

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.**

![](https://i.imgur.com/NhD00VJ.png)



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

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

Let `i` be the intersection node.

![](https://i.imgur.com/5nk9q8A.png)

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.

![](https://i.imgur.com/HANSCU3.png)

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

![](https://i.imgur.com/r97HlNm.png)


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

![](https://i.imgur.com/8ZKFKRp.png)

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

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