  Given a rooted tree T, the level ancestor problem aims to answer queries of
the form LA(v, d), which identify the level d ancestor of a node v in the tree.
Several algorithms of varied complexity have been proposed for this problem in
the literature, including optimal solutions that preprocess the tree $T$ in
linear bounded time and proceed to answer queries in constant time. Despite its
significance and numerous applications, to date there have been no comparative
studies of the performance of these algorithms and few implementations are
widely available. In our experimental study we implemented and compared several
solutions to the level ancestor problem, including three theoretically optimal
algorithms, and examined their space requirements and time performance in
practice.

Data Structures and Algorithms