# mmap(blog)

# Flat in-order binary trees

Published: 2023-08-13

- Abstract
- Background
- Nomenclature
- Addressing tree nodes
- Traversing perfect binary trees
- Traversing left-perfect binary trees
- Extensible segment trees

## Abstract

This article is an in-depth guide to the flat in-order representation of binary trees. We derive efficient operations to navigate these trees, such as finding the tree root and computing the parent and children for each node. We then use this flat representation to implement a novel efficient data structure: extensible segment trees.

## Background

Authenticated data structures are essential in distributed systems (e.g., version control systems and blockchains). Binary Merkle trees are among the most common approaches to authenticated data structures.

Building a Merkle tree from scratch for an arbitrary data structure is straightforward and can be mechanizedSee, for example, Authenticated Data Structures, Generically by Andrew Miller et al..
A more interesting question is how to update existing Merkle trees incrementally to reflect changes in the underlying data structure.
For example, adding a new item to a sequence of N data blocks requires recomputing about log_{2}(N) hashes.

Furthermore, storing Merkle trees for a linear sequence of data blocks explicitly (i.e., as explicit tree nodes with pointers) is wasteful. Finding an implicit encoding mapping the tree onto an array of 2N-1 hashes reduces storage space significantly.

The most common approach to packing a tree into an array used in binary heaps and segment trees is to place children of node at index i at positions 2i+1 and 2i+2. This approach works well for fixed-size arrays, but it's inefficient for growable arrays because adding a new data block might require O(N) data moves.

The DAT protocol pioneered an alternative approach, flat in-order trees. This scheme interleaves interior node hashes and data hashes. A tree with N data blocks requires 2N-1 slots, with i-th data block hash stored at index 2i. The interior hashes reside at odd indices between the data block hashes. This scheme fixes the data node locations (slots with even indices contain leaf data nodes) and allows updating internal nodes efficiently.

Unfortunately, the way DAT protocol defines trees is somewhat awkward: it treats the sequence as a forest of perfect binary trees, not a single binary tree. Furthermore, the specification doesn't contain enough details on how to navigate the flat tree efficiently.

This article describes an intuitive model for flat in-order tree navigation and suggests efficient routines for computing the parent and children of any tree node.

## Nomenclature

We will consider two types of trees.
First, we'll analyze the case of *perfect binary trees* (`PBT`

), i.e., binary trees in which all interior nodes have two children and all leaves have the same depth.
These trees correspond to sequences of 2^{K} data blocks and contain 2^{K+1}-1 nodes.

Second, we'll generalize perfect trees to handle sequences of any N data blocks.
There is no established name for such trees, so we'll call them *left-perfect binary trees* (`LPBT`

).
A left-perfect tree with N leaves is either a perfect tree or a fork where the left child is a perfect tree containing at least N/2 leaves, and the right child is a left-perfect tree containing the rest of the leaves.

## Addressing tree nodes

We'll first examine addressing nodes within a flat in-order perfect binary tree and then extend the approach to left-perfect binary trees.

theorem: in a flat in-order perfect binary tree of depth D, node's index i has the following structure:

- The longest run of least-significant set bits in i's binary representation indicates the depth of subtrees rooted at i. If i's binary representation has the last K bits set, i's children are subtrees of depth K.
- The bits before the last zero signify the path to node i starting from the tree root. Zeros indicate left turns; ones indicate right turns.

proof: by induction on the tree depth D.

Base case: the theorem is vacuously true for trees of depth one (a single node with index zero). The case of a tree of depth two is more instructive:

Induction step: let's assume that the theorem holds for trees of depth D and consider a tree of depth D+1.

The root of a D+1-tree resides at index 2^{D}-1, so its binary representation is 011..1, with precisely D least-significant bits set.
The binary representation of indices in the left subtree starts with zero, followed by a D-tree address.
The binary representation of indices in the right subtree begins with one, followed by a D-tree address.
Hence, the addressing scheme preserves as we increase the tree depth from D to D+1.
∎

## Traversing perfect binary trees

We'll need two primitive bit-twiddling operations for the tree navigation: locating the last zero bit of a number and rounding a number up to a power of twoAll code in this article is in the C programming language and complies with the C11 standard..

```
#include <assert.h>
#include <stdint.h>
```*// Isolates the last set bit of number N.*
uint64_t LastSetBit(const uint64_t n) {
return n - ((n - 1) & n);
}
*// Isolates the last unset bit of number N.*
uint64_t LastZeroBit(const uint64_t n) {
return LastSetBit(n + 1);
}
*// Rounds the argument up to the next highest power of two.*
uint64_t RoundUpPowerOf2(uint64_t n) {
// See Bit Twiddling Hacks.
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
n++;
return n;
}

We are now ready to define the tree navigation functions. The addressing scheme proof suggests the function for locating the tree root: we divide the tree size by two.

*// Computes the root of the perfect binary tree of the given SIZE.*
uint64_t PBT_Root(const uint64_t size) {
assert(size == 1 || RoundUpPowerOf2(size) == size + 1);
return size >> 1;
}

Next, let's consider locating the parent of node i. According to the scheme, we must find the last zero in the binary representation of i, set it to one, and set the next most significant bit to zero.

*// Computes the parent of node I in a perfect binary tree.*
uint64_t PBT_Parent(const uint64_t i) {
return (LastZeroBit(i) | i) & ~(LastZeroBit(i) << 1);
}

Finally, the parent computation suggests procedures for locating the children. We must find the last zero bit k in the node's binary representation. For the left child, we must set bit k-1 to zero. For the right child, we also need to set bit k to one.

*// Computes the left child of node P in a perfect binary tree.*
*// Requires: P is not a leaf.*
uint64_t PBT_LeftChild(const uint64_t p) {
assert(p & 1);
return p & ~(LastZeroBit(p) >> 1);
}
*// Computes the right child of node P in a perfect binary tree.*
*// Requires: P is not a leaf.*
uint64_t PBT_RightChild(const uint64_t p) {
assert(p & 1);
return (p | LastZeroBit(p)) & ~(LastZeroBit(p) >> 1);
}

Next, we'll generalize these functions to handle left-perfect binary trees.

## Traversing left-perfect binary trees

The left subtree of a left-perfect binary tree is a perfect binary tree by definition. Hence the formula for the left child we developed for perfect binary trees works as-is.

*// Computes the left child in a flat in-order left-perfect binary tree.*
uint64_t LPBT_LeftChild(const uint64_t i) { return PBT_LeftChild(i); }

We need three more operations to efficiently navigate a left-perfect binary tree: finding the tree root and computing the node's parent and right child. Left-perfect binary tree structure changes with the node count, so the latter two functions will depend on the node index and the tree node count.

In a left-perfect binary tree, the tree root is the same node that the smallest perfect binary tree with at least the same number of nodes would have. Thus, given the number of tree nodes, we compute the root of the smallest perfect tree containing the input tree.

*// Computes the root of a left-perfect binary tree of the given SIZE.*
uint64_t LPBT_Root(const uint64_t size) {
return PBT_Root(RoundUpPowerOf2(size + 1) - 1);
}

Another way to view left-perfect binary trees is to imagine them as perfect binary trees with some trailing nodes removed.
The remaining nodes are reattached to the closest existing parent to keep the tree complete.
This observation gives us a simple way to compute the node's parent:
We apply the `PBT_Parent`

function until the computed node falls within the tree bounds.

*// Computes the parent of node I in a left-perfect binary tree of the given SIZE.*
uint64_t LPBT_Parent(uint64_t i, const uint64_t size) {
do { i = PBT_Parent(i); } while (i >= size);
reutrn i;
}

Our observations give us two algorithms for computing the right child.
Notice that the `PBT_RightChild`

function gives correct results if the output value falls within the tree bounds.
If the outcome falls outside the tree bounds, the recursive definition of left-perfect trees implies that the right child must be the root of the right subtree.

*// Computes the right child of node I in a left-perfect binary tree of the given SIZE.*
uint64_t LPBT_RightChild(const uint64_t i, const uint64_t size) {
assert(n & 1);
const uint64_t r = PBT_RightChild(i);
return (r < size) ? r : i + 1 + LPBT_Root(size - i - 1);
}

Alternatively, if `PBT_RightChild`

's result falls outside of the tree, we can follow the left links in the “virtual” perfect tree until we hit the tree bounds again.

*// Computes the right child of node I in a left-perfect binary tree of the given SIZE.*
uint64_t LPBT_RightChild_2(const uint64_t i, const uint64_t size) {
assert(n & 1);
uint64_t r;
for (r = PBT_RightChild(n); r < size; r = PBT_LeftChild(r));
return r;
}

We now have enough tools to navigate any left-perfect binary tree efficiently.

## Extensible segment trees

Merkle trees are a special case of segment trees. Traditional representations of segment trees allow efficient updates, but they don't support appending new items to the sequence. Flat in-order representation for segment trees opens a path to an efficient append operation.

This section presents an implementation of segment trees designed for answering range sum queries. The same approach will work for any problem where node elements and the aggregation operation form a semigroup.

We'll need a new operation to support efficient range queries: finding the lowest common ancestor (LCA) of two leaves in a left-perfect binary tree. The tree addressing scheme suggests a simple way to compute LCA for leaves because their paths from the root node are aligned. We must find the most significant bit where the leaves differ, set this bit to zero, and set all lower bits.

*// Extracts the most significant bit from number N.*
uint64_t MostSignificantBit(uint64_t n) {
int i = 0;
while (n >>= 1) i++;
return 1 << i;
}
*// Computes the lowest common ancestor of leaves X and Y in a left-perfect*
*// binary tree.*
uint64_t LPBT_LeavesLCA(const uint64_t x, const uint64_t y) {
assert(!(x & 1));
assert(!(y & 1));
if (x == y) return x;
const uint64_t d = MostSignificantBit(x ^ y);
return (x & ~d) | (d - 1);
}

We can now proceed with the segment tree implementation. Let's define the data structures representing the tree.

*// The type of values stored in the tree nodes.*
typedef int64_t value_t;
*// The maximum number of nodes in the tree.*
const size_t MAX_NODES = 10001;
*// The current number of nodes in the tree.*
*// Invariant: G_NumNodes <= MAX_NODES*
*// Invariant: G_NumNodes == 0 || G_NumNodes % 2 == 1*
size_t G_NumNodes;
*// The flat in-order representation of the tree.*
*// Even elements correspond to the sequence items.*
value_t G_Nodes[MAX_NODES];

We highlight that the trees work with any semigroup by extracting the combining operator into a separate function.

```
value_t Combine(const value_t x, const value_t y) {
return x + y;
}
```

We then define procedure `ST_Set`

updating the sequence.
It sets the corresponding leaf value and traverses the tree upwards, recomputing the parent node values.

*// Updates the sequence to contain the given ITEM at the specified POSITION.*
void ST_Set(const size_t position, const value_t item) {
assert(G_NumNodes > 0);
assert(position <= G_NumNodes / 2);
size_t i = position * 2;
G_Nodes[i] = item;
if (G_NumNodes == 1) return;
size_t root = LPBT_Root(G_NumNodes);
do {
i = LPBT_Parent(i, G_NumNodes);
G_Nodes[i] = Combine(
G_Nodes[LPBT_LeftChild(i)],
G_Nodes[LPBT_RightChild(i, G_NumNodes)]
);
} while (i != root);
}

The `ST_Append`

procedure adds an item to the sequence and updates the tree accordingly.
The empty sequence is a special case because there are no interior nodes to update.
In the case of non-empty sequences, the procedure adds a new interior node and a leaf and delegates the rest to the previously defined `ST_Set`

procedure.

```
// Appends the given ITEM to the sequence.
void ST_Append(const value_t item) {
assert(G_NumNodes + 2 <= MAX_NODES);
if (G_NumNodes == 0) {
G_Nodes[G_NumNodes++] = item;
} else {
G_NumNodes += 2;
ST_Set(G_NumNodes / 2, item);
}
}
```

The `ST_Sum`

function computing the sum of sequence items in the specified range is the most involved part of the implementation.
It relies on the `LPBT_LeavesLCA`

function to compute the LCA of the two leaves corresponding to the requested bounds.
It then traverses the tree from the left bound to the LCA node, summing all unaccounted *right* subtrees on the way up.
It does the same for the right bound, summing all unaccounted *left* subtrees on the path.

*// Computes the sum of the sequence items in the index interval [l, r].*
value_t ST_Sum(const size_t l, const size_t r) {
assert(r * 2 < G_NumNodes);
assert(l <= r);
uint64_t i = l * 2;
uint64_t j = r * 2;
if (i == j) return G_Nodes[i];
const uint64_t lca = LPBT_LeavesLCA(i, j);
value_t acc = Combine(G_Nodes[i], G_Nodes[j]);
*// Traverse the tree upwards from the left bound and sum up all*
*// the right subtrees on the way.*
while (1) {
const uint64_t p = LPBT_Parent(i, G_NumNodes);
if (p == lca) break;
const uint64_t rc = LPBT_RightChild(p, G_NumNodes);
if (rc != i) acc = Combine(acc, G_Nodes[rc]);
i = p;
}
*// Traverse the tree upwards from the right bound and sum up all*
*// the left subtrees on the way.*
while (1) {
const uint64_t p = LPBT_Parent(j, G_NumNodes);
if (p == lca) break;
const uint64_t lc = LPBT_LeftChild(p);
if (lc != j) acc = Combine(acc, G_Nodes[lc]);
j = p;
}
return acc;
}

The `ST_Append`

, `ST_Set`

, and `ST_Sum`

procedures provide a working implementation of extensible segment trees.