Algorithms on Strings, Trees and Sequences

8

Constant-Time Lowest Common Ancestor Retrieval

8.1. Introduction

We now begin the discussion of an amazing result that greatly extends the usefulness of suffix trees (in addition to many other applications).

Definition In a rooted tree , a node u is an ancestor of a node v if u is on the unique path from the root to v. With this definition a node is an ancestor of itself. A proper ancestor of v refers to an ancestor that is not v.

Definition In a rooted tree , the lowest common ancestor (lca) of two nodes x and y is the deepest node in that is ...