We present a deterministic algorithm that given a tree T with n vertices, a
starting vertex v and a slackness parameter epsilon > 0, estimates within an
additive error of epsilon the cover and return time, namely, the expected time
it takes a simple random walk that starts at v to visit all vertices of T and
return to v. The running time of our algorithm is polynomial in n/epsilon, and
hence remains polynomial in n also for epsilon = 1/n^{O(1)}. We also show how
the algorithm can be extended to estimate the expected cover (without return)
time on trees.