Proof of correctness: Algorithm for diameter of a tree in graph theory
Let’s call the endpoint found by the first BFS x. The crucial step is proving that the x found in this first step always “works” — that is, that it is always at one end of some longest path. (Note that in general there can be more than one equally-longest path.) If we can establish … Read more