node package manager



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.


var preprocessTree = require("least-common-ancestor")
//Create some random tree 
var 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 queries 
var lca = preprocessTree(tree)
//Now we get constant time least common ancestor queries! 
var assert = require("assert")
assert.ok(lca(tree.baz.zardoz.potato, === tree)
assert.ok(lca(tree.baz.zardoz.potato, tree.baz.zardoz.golub) === tree.baz.zardoz)


npm install least-common-ancestor


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 of node

    • 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 and b are objects which are subnodes of the tree

Returns The object in the tree which is the least common ancestor of a and b


Rebuilds the data structure from scratch. This is necessary if the structure of the tree changes.


(c) 2014 Mikola Lysenko. MIT License