A Simple Solution to the Level-Ancestor Problem

2019/03/04 by Gaurav Menghani, Menghani, Gaurav, Dhruv Mátáni +1
Computer Science · #Algorithms and Data Compression #Data Management and Algorithms #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1903.01387

openalex publication_date 2019/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A Level Ancestory query LA(u, d) asks for the the ancestor of the node u at a depth d. We present a simple solution, which pre-processes the tree in O(n) time with O(n) extra space, and answers the queries in O(log n) time. Though other optimal algorithms exist, this is a simple enough solution that could be taught and implemented easily.

Related

• Static Level Ancestors in Practice
• Still Simpler Static Level Ancestors
• Simpler O(1) Query Algorithm for Level Ancestors
• The Euler Path to Static Level-Ancestors
• Size-constrained Weighted Ancestors with Applications