Constant-Time Lowest Common Ancestor Retrieval
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 ...