node package manager


Index calculations for inorder layout of balanced binary trees


Operations on nodes for balanced binary trees stored in in-order layout. These are useful if you are building data structures, like binary search trees, implicitly (ie not storing pointers to subtrees).


npm install inorder-tree-layout


Suppose we have a tree with 10 elements, packed in level order. Then the inorder labelling of this tree looks like the following picture:

The tree:
        /   \
       3     8
      / \   / \
     1   5 7   9
    / \  |
   0   2 4

Now given this tree, here is how we can compute some queries using this library:

var layout = require("inorder-tree-layout")
console.log(layout.left(10, 3))     //Prints:  1 
console.log(layout.parent(10, 7))   //Prints:  8 
console.log(layout.height(10, 9))   //Prints:  0 


var layout = require("inorder-tree-layout")


  • n is always the size of the tree
  • x is the index of a node in the tree


Returns the index of the root of a tree of size n.


Returns the index of the first node of the tree


Returns the index of the last node in the tree

layout.height(n, x)

Returns the height of node x in a tree of size n

layout.prev(n, x)

Returns the predecessor of x in an in-order traversal, x)

Returns the successor of x in an in-order traversal

layout.parent(n, x)

Returns the parent of x in a tree of size n

layout.left(n, x)

Returns the left child of x

layout.right(n, x)

Returns the right child of x

layout.leaf(n, x)

Returns true if x is a leaf node.

layout.lo(n, x)

Returns the left most ancestor of x in the tree

layout.hi(n, x)

Returns the right most ancestor of x in the tree


(c) 2013 Mikola Lysenko. MIT License