least-common-ancestor
Preprocesses a tree encoded as some generic JSON object so that least common ancestor queries can be answered in O(1) time and O(n log(n)) space. This is a static operation, so if you modify the tree you will need to rebuild the data structure.
Example
var preprocessTree = //Create some random treevar tree = bar: name: "bar" baz: name: "baz" zardoz: golub: {} potato: x: 1 y: 2 z: 3 f: p: 1 q: {} xx: {} {} {} //Preprocess tree to answer least common ancestor queriesvar lca = //Now we get constant time least common ancestor queries!var assert = assertassert
Install
npm install least-common-ancestor
API
var lca = require("least-common-ancestor")(root[,childrenOf(node)])
Preprocesses a tree to answer least common ancestor queries
-
root
is the root of a JSON object tree -
childrenOf(node)
is an optional function which returns an array of children ofnode
node
is the subtree node
childrenOf
should return an array of all possible children of node
Returns A function, lca
, which computes the least common ancestor of any two nodes of the tree.
lca(a, b)
Computes the least common ancestor of two nodes in a tree
a
andb
are objects which are subnodes of the tree
Returns The object in the tree which is the least common ancestor of a
and b
lca.rebuild()
Rebuilds the data structure from scratch. This is necessary if the structure of the tree changes.
Credits
(c) 2014 Mikola Lysenko. MIT License