# Crate flat_tree

Expand description

## Series of functions to map a binary tree to a list

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

``````                                    15
7                                             23
3                 11                      19                      27
1       5        9          13          17          21          25          29
0   2   4   6   8    10    12    14    16    18    20    22    24    26    28    30...
``````

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    8    10    12    14
``````

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

## Functions

• Returns both children of a node.
• Returns how many nodes are in the tree that the node spans.
• Returns how many leaves are in the tree that the node spans.
• Returns the depth of a node.
• Returns a list of all the full roots (subtrees where all nodes have either 2 or 0 children) `<` index.
• Returns the flat-tree of the tree node at the specified depth and offset.
• Returns only the left child of a node.
• Returns the left most node in the tree that it spans.
• Returns the offset of a node.
• Returns the parent of a node with a depth.
• Returns only the left child of a node.
• Returns the right most node in the tree that the node spans.
• Returns the sibling of a node.
• Returns the left and right most nodes in the tree that the node spans.
• Returns the parent’s sibling, of a node.