Awesome

flat-tree

Map a binary tree to a list. Common Lisp implementation, adapted from mafintosh/flat-tree.

> (flat-tree:parent 0)
1

You can represent a binary tree in a simple flat list using the following structure:

      3
  1       5
0   2   4   6  ...

Each number represents an index in a flat list. So a tree:

      A
  B       C
D   E   F   G  ...

would be represented as a list: [D B E A F C G]

Furthermore, indexes 0, 2, 4, 6 are on depth 0. 1, 5, 9 on depth 1. And so forth.

depth = 2  ^        3
depth = 1  |    1       5
depth = 0  |  0   2   4   6  ...

In some cases it is also useful to calculate an offset. Indexes 0, 1, 3, 7 have an offset 0:

                (7)
       (3)
  (1)       5
(0)   2   4   6      ...

2, 5, 11, 23 offset 1:

                 7
       3                  (11)
  1        (5)        9          13
0   (2)   4   6    10   12    14    15

This module exposes a series of functions to help you build and maintain this data structure.