This is the solution. The question I can't tell cause I agreed not to share. I guess there might be another way of solve it, but it does not take away the meaning here, asking very complex problem over the phone is not a good way of figuring out if the candidate would be great on the team.
I'm guessing this is not the complete question, rigth? Because you can only find a Hamiltonian path if the tree itself is a path.