I have a tree. This tree has no particular root (free-tree). I want to find a path that visit all nodes. This path has to be the shortest possible.
All edges are considered to have a distance of 1.
My problem is not finding a Hamiltonian path, because I don't have any restriction on the number of times a node can be visited.
We don't know the source node of the path. The source has to be one allowing us to find the shortest path visiting all nodes.
Hint: Start from a source $s \in V$ to visit all vertices that $V$ is the set of vertices of the tree. All edges are visited twice except those which contribute to the longest path.
Then, the shortest possible path, visiting all nodes, is equal to $2 \times |E| - |P_{L}|$, where $|E|$ denotes the number of edges, and $|P_{L}|$ is the number of edges in the longest path. This can be achieved with time complexity $O (E)$.
In a DFS traversal of the tree (starting from an arbitrary node) every edge is traversed twice: once down and once up. Some of these edges need not be traversed down.
Say your DFS traverses the children from left to right. Then the edges drawn in red in the following figure need to be traversed once only (we don't need to traverse them on the way back from the deepest node).
Now we want to find a red path that is as long as possible. This is known as the diameter of the tree and it can be found in linear time. The diameter of the tree above is equal to 5 for example.
