  We present algorithms that run in linear time on pointer machines for a
collection of problems, each of which either directly or indirectly requires
the evaluation of a function defined on paths in a tree. These problems
previously had linear-time algorithms but only for random-access machines
(RAMs); the best pointer-machine algorithms were super-linear by an
inverse-Ackermann-function factor. Our algorithms are also simpler, in some
cases substantially, than the previous linear-time RAM algorithms. Our
improvements come primarily from three new ideas: a refined analysis of path
compression that gives a linear bound if the compressions favor certain nodes,
a pointer-based radix sort as a replacement for table-based methods, and a more
careful partitioning of a tree into easily managed parts. Our algorithms
compute nearest common ancestors off-line, verify and construct minimum
spanning trees, do interval analysis on a flowgraph, find the dominators of a
flowgraph, and build the component tree of a weighted tree.
