The Level Ancestor Problem simplified

Michael A. Bender, Martín Farach-Colton

Research output: Contribution to journalConference articlepeer-review

112 Scopus citations

Abstract

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
Volume321
Issue number1
DOIs
StatePublished - Jun 16 2004
EventLatin American Theoretical Informatics - Cancun, Mexico
Duration: Apr 3 2002Apr 6 2002

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Data structures
  • Level Ancestor Problem
  • Rooted trees

Fingerprint

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

Cite this