The Level Ancestor Problem simplified

Michael A. Bender, Martín Farach-Colton

    Research output: Contribution to journalConference articlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)5-12
    Number of pages8
    JournalTheoretical Computer Science
    Issue number1
    StatePublished - Jun 16 2004
    EventLatin American Theoretical Informatics - Cancun, Mexico
    Duration: Apr 3 2002Apr 6 2002


    • Data structures
    • Level Ancestor Problem
    • Rooted trees

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'The Level Ancestor Problem simplified'. Together they form a unique fingerprint.

    Cite this