The level Ancestor problem simplified

Michael A. Bender, Martín Farach-Colton

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We present a very 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 thus: preprocess a given rooted tree T to answer 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)
    Title of host publicationLATIN 2002
    Subtitle of host publicationTheoretical Informatics - 5th Latin American Symposium, Proceedings
    EditorsSergio Rajsbaum
    PublisherSpringer Verlag
    Number of pages8
    ISBN (Electronic)3540434003, 9783540434009
    StatePublished - 2002
    Event5th Latin American Symposium on Theoretical Informatics, LATIN 2002 - Cancun, Mexico
    Duration: Apr 3 2002Apr 6 2002

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other5th Latin American Symposium on Theoretical Informatics, LATIN 2002

    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