Skip to main content
eScholarship
Open Access Publications from the University of California

A linear time algorithm for the lowest common ancestors problem

Abstract

We investigate two lowest common ancestors (LCA) problems on trees. We give a linear time algorithm for the off-line problem, on a random access machine (RAM). The half-line problem is one in which LCA queries on a fixed tree are arriving on line. We extend our RAM algorithm to answer each individual query in 0(1) time, with 0(n) preprocessing time. Tarjan observed that this result helps to explicate the difference in power between RAM and pointer machines. We also show how to modify our algorithm to achieve a linear preprocessing time, optimal query time, algorithm on a reference machine.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View