§ Diameter of a tree
§ Key property of the diameter
- Let be a path of maximum diameter, which starts at and ends at . Consider a tree where the diameter is shown in golden:
- We claim that a node at distance from the left can have a subtree of height at most :
- Suppose this were not the case. Then, we can build a longer diameter (in pink) that is longer than the "supposed diameter" (in gold):
§ Algorithm to find the diameter:
First perform DFS to find a vertex "on the edge", say . Then perform DFS again
starting from this vertex . The farthest vertex from , say gives
us the diameter (the distance from to )
§ Proof by intuition/picture:
- first imagine the tree lying flat on the table.
- Hold the tree up at node . It's going to fall by gravity and arrange as shown below. This is the same as performing a DFS.
- Pick one of the lowest nodes (we pick ). Now hold the entire tree from this lowest node, and once again allow gravity to act.
- This will give us new lowest nodes such as . This node is going to be diameter, "because" it's the distance from a lowest node to another lowest node.