Static Level Ancestors In Practice

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 the significance and numerous applications of the level ancestor problem, to date there have been no comparative studies of the performance of published 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.