# Shortest path visiting all nodes in an unrooted tree

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.

• What have you tried? Where did you get stuck? What approaches have you considered and rejected, and why? We don't want to just do your exercise for you. We want to help you gain understanding, but as it is not clear what your specific problem is, it's not clear how to help. Assuming you've tried to solve it, please edit the question to show your thoughts and the answers to these questions. If you haven't made a serious effort to try to solve it on your own, you should do that before posting here. – D.W. Oct 20 '15 at 2:01
• So what other restrictions do you have for the algorithm? – Juho Oct 20 '15 at 7:03

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)$.