Data.RangeMin.LCA

Functions for finding lowest common ancestors in trees in O(1) time, with O(n) preprocessing.

Documentation

type Index = Int

Index is used as a node identifier, so that the user can refer to tree nodes in a random-access fashion.

lowestCommonAncestor :: Int -> (a -> Index) -> Tree a -> Index -> Index -> a

lowestCommonAncestor n ix tree takes a tree whose nodes are mapped by ix to a unique index in the range 0..n-1, and returns a function which takes two indices (corresponding to two nodes in the tree) and returns the label of their lowest common ancestor.

This takes O(n) preprocessing and answers queries in O(1), as it is an application of Data.RangeMin.

For binary trees, consider using Data.RangeMin.LCA.Binary.

quickLCA :: Tree a -> (Int, Tree (Index, a), Index -> Index -> (Index, a))

Takes a tree and indexes it in depth-first order, returning the number of nodes, the indexed tree, and the lowest common ancestor function.