Lowest Common Ancestor Algorithms

[berkay-top]

This is a(n):

• New algorithm
• Update to an existing algorithm
• Error
• Proposal to the Repository

Details:

The lowest common ancestor of two nodes of a rooted tree is the lowest node
whose subtree contains both the nodes. A typical problem is to efficiently process
queries that ask to find the lowest common ancestor of two nodes. I want to implement two solutions for that problem. One with binary lifting and one with sparse table in C++.