Yesterday I learned a cool algorithm, which can be intuitively described as follows:
Pick a starting node, walk as far as you can, turn around, and walk as far as you can again.
Doesn’t sound too complicated, right? But it actually solves a non-trivial problem: it finds the diameter of a tree in linear computation time. The diameter of a tree is the length of the longest possible walk on it. For example, the tree below has diameter 8, because the longest walk on it goes through 8 links. There are actually three walks of length 8, we show the one between nodes p and q:
