# 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

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

### Implementation

## Proof

### Properties of Trees

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

### Proof by Contradiction

- 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**. - Why we run
**BFS**on an arbitrary node**s**will alway end with**u**?- 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. - Assuming we start at node
**s**.- If
**s**is**u**, then we will always end with**v**by the first**BFS**, and the second**BFS**we get**u**again. - If
**s**is not**u**and we end with a node**x**distinct than**u**and**v**using**BFS**.- 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. - 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.

- If the path of

- If

- Let

## Reference

- MIT - Introduction to Algorithms: Problem Set 9 Solutions
- Algorithm to find diameter of a tree using BFS/DFS
- 树的直径及其性质与证明
- SPOJ PT07Z - Longest path in a tree
- POJ Cow Marathon
- Diameter of a Binary Tree
- Tree