Data.RangeMin.LCA.Binary

Functions for finding lowest common ancestors in binary 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.

data BinTree a

A generic binary tree.

Constructors

Tip

BinTree a (BinTree a) (BinTree a)

quickLCABinary :: BinTree a -> (Int, BinTree (Index, a), Index -> Index -> (Index, a))

Takes a binary tree and indexes it inorder, returning the number of nodes, the indexed tree, and the lowest common ancestor function.

lcaBinary :: Int -> (a -> Index) -> BinTree a -> Index -> Index -> a

Similar to LCA.lowestCommonAncestor, but optimized for binary trees. This method can reasonably be expected to run twice as fast as lowestCommonAncestor.