Dynamic Programming21 sections · 916 units
Open in Course

Challenge: Finding the Actual Path

Reconstructing the diameter

The diameter DP gives the length, but what about the actual path? Track which children give the two longest depths. At the node where the maximum occurs, you have two endpoints.

From each, trace back through the tree. Alternative: run BFS from any node to find the farthest node uu. Then BFS from uu to find the farthest node vv. The path uvu \to v is the diameter. The two-BFS approach is simpler to implement when you need the actual path, not just the length.