1. Definition
  2. Finding The Diameter of N-Ary Tree
    1. Greedy Algorithm
    2. Implementation
  3. Proof
    1. Properties of Trees
    2. Proof by Contradiction
  4. Reference

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

Implementation

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