# 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