 # Tree Diameter

Author: Dalao Date: 2020-03-07
Tree Diameter

# Tree Diameter

## Definition

The diameter of a tree is the distance of the longest path between two end nodes $\arg\max_{(u, v) \in G}d(u, v)$, where $d(u, v)$ is the distance function. It has many applications on tree problems and often a high complexity solution can be changed to a linear solution with the property of the tree diameter.

## Finding The Diameter of N-Ary Tree

### Greedy Algorithm

1. Run BFS to find the farthest node u starting from an arbitrary node said s
2. Then run BFS from u to find the farthest node v
3. Distance between node u and v is the diameter of given tree

PT07Z

P1985CowMarathon

## Proof

### Properties of Trees

1. Between any 2 nodes in a tree there is exactly one path
2. Any node can serve as the root of the tree

### Proof by Contradiction

1. Assuming one end of the diameter u is known, the other end must be the node v furthest from this end. We can find it by using BFS, the last discovered node is v.
2. Why we run BFS on an arbitrary node s will alway end with u?
1. Let u and v be any two nodes such that d(u, v) is the diameter of the tree. There is a unique path from u to v because of tree properties.
2. Assuming we start at node s.
1. If s is u, then we will always end with v by the first BFS, and the second BFS we get u again.
2. If s is not u and we end with a node x distinct than u and v using BFS.
1. If the path of (x, u) does not intersect with the path of (u, v), the d(x, u) + d(u, v) > d(u, v), contradiction.
2. If the path of (x, u) intersect with (u, v) at y, then d(x, y) > d(u, y) since we know when we started the search from s, x is deeper than u, then d(x, y) + d(y, v) > dis(u, v). contradiction.

## Reference 