Tree Algorithm

ian londonperlmongers at
Thu Dec 31 15:42:01 GMT 2009

I am frustrated in that I think I know of an algorithm for a tree (not a 
christmas tree!) but can't remember it's name and that makes it much 
more difficult to google.

Anyone know (from my attempt at a description) what this algorithm is 
called? Even better, is there a CPAN module for it?

  * Every node has a left and a right value and a level
  * For any given node, all of it's descendents left values lie between 
the nodes left and right values.
  * For a leaf node, it's right value equals it's left value + 1
  * All children of a parent will therefore be those with node numbers 
between the parents left and right values and one level deeper.

I remember it being easy to use this in a database since it makes it 
possible to get (for example) all descendents or all children in a 
single query, something not always possible with other algorithms. I 
also seem to remember that it also makes it easier to move a sub-tree 
since it is then just a matter of applying a constant offset to all the 
left and right pointers of the sub-tree.

(After describing it here I could probably write the Perl code myself 
now, but I would still like to know the name of the algorithm)

Any takers?


More information about the mailing list