The problem
Given a rooted tree with n nodes, where all leaves are labelled from a set of labels. Build a datastructure which, given a leaf node, a and a label l, can find the lowest ancestor, u, of a, where u has at least one descendant with label l.
Linear Space / Linear Time approach
- Start at leaf a
- Examine all siblings of a
- If a sibling has label l find the lowest-common-ancestor between a and that sibling.
- Otherwise continue to parents
- If all leaf-nodes descending from parents are not labelled l, continue to the grandparents and check their leaf-node descendants.
- Continue recursively checking greater-grandparents and all their descendant leaf-nodes until an l-labelled descendant is found.
This has time complexity O(n) and space complexity O(n).
Is there a faster way to do this with linear space complexity? Perhaps by preproccessing the tree somehow? l and a are not fixed so the pre-processing has to be flexible.
The lowest common ancestor can be found in constant time using RMQ via Eulerian-Tour.
Keep in mind the tree is not balanced or sorted in any way.
Here is a solution with O(log(n)^3) time complexity and O(n log(n)) space complexity.
Let
L
be the list of labels that you encounter on the Eulerian Path. You build a Segment Tree with this list, and store in each node of the tree the set of labels appearing in the corresponding segment. Then you can check in O(log(n)^2) time, if a label appears in a subtree via a range query in the segment tree.To find the correct parent, you can do a binary search. E.g. something similar to binary lifting. Which will add another factor of log(n).