The Level Ancestor Problem simplified

We present a simple algorithm for the Level Ancestor Problem. A Level Ancestor Query LA(v, d) requests the depth d ancestor of node v. The Level Ancestor Problem is to preprocess a given rooted tree T to support level ancestor queries. While optimal solutions to this problem already exist, our new optimal solution is simple enough to be taught and implemented.

Authors

• Michael A. Bender
• Martı́n Farach-Colton

Keywords

• Data structures
• Rooted trees
• Level Ancestor Problem