Lowest Common Ancestor

Define the Lowest Common Ancestor Problem. I.e. what does LCA(i,j) return?

How is a Euler tour different to a depth first search?

How long is the Euler tour of a preprocessed LCA tree?

Describe how to preprocess a tree ready for an LCA query.

Describe how to make a LCA query when solved using RMQs.

Without using the +/- RMQ algorithm. What is the prep time, space and query time complexity of the LCA solution using RMQs?

If the +/- RMQ problem can be solved with O(n) space, O(n) prep time and O(1) query time, what is the space, prep time and query time complexity for LCAs when solved using the +/- RMQ algorithm?

How can RMQs be solved in O(1) query time and O(n) space/prep time?