@singku

proof of :

"Randomly select a node x as the root, do a dfs/bfs to find the node y that has the longest distance from x.

Then y must be one of the endpoints on some longest path."

x is root of the tree.

Longest path in a tree == max(height(node.left)+height(node.right)+1) for all nodes.

Let pathLen(node) = height(node.left)+height(node.right)+1

Let m be the node which has maximum pathLen(node) amongst all nodes.

Can m's longest path avoid 'y'?

m's subtree doesn't contain y. Then find the Lowest Common Ancestor of m and y. pathLen(LCA) > pathLen(m), because

pathLen(LCA) >= height(LCA) + height(m) >= height(m)*2 >= pathLen(m). Contradiction!
m's subtree contains y. y has the greatest depth out of any leaf node, so it's almost trivial. eg. if y is in m.left.subtree, then the longest path from m to a leaf node in m.left.subtree obviously goes to y.