Graph Theory37 sections · 1633 units
Open in Course

Concept - General Tree Diameter

Double BFS for general trees

What if the tree is not binary? What if a node has 1010 children? You could modify the previous approach, but there is a simpler algorithm that works for any tree: Double BFS. The idea:

1.1. Start from any node and find the furthest node from it.

2.2. From that node, find the furthest node again.

The distance in step 22 is the diameter. This works because the furthest node from any starting point is always one endpoint of the diameter.