The C++ logo, by Jeremy Kratz, licensed under CC0 1.0 Universal Public Domain Dedication

constexpr tree structures

Notes published the 09 Aug, 2021
14 - 18 minutes to read, 3564 words
Categories: c++
Keywords: bfs, c++, constants, constexpr, dfs, iterator, performance, view types

Table of Contents

A node-based binary tree
- No parent reference
- Traversing the tree
Binary array tree
- bfs traversal
- dfs traversal
ternary and n-ary node-based trees
ternary and n-ary array tree
- bfs traversal
- dfs traversal
Non-full n-ary array trees

This is a follow-up of my notes about a constexpr linked list.

A `node`-based binary tree

The same consideration for a linked list holds, a node won’t use pointers but const references, and it won’t have user-defined constructors (even defaulted). Given this limitation in the design space, there are also the same usability issues, until the already reported compiler bugs are fixed.

For simplicity, let’s see how a node-based binary tree can be implemented.

struct data{int i;};

struct node {
	data d;
	const node &left;
	const node &right;
};

constexpr const node Null{data{0},Null,Null};

constexpr node leaf(data d){
	return node{d, Null, Null};
}

constexpr const node tree
{
	data{1},
	node
	{
		data{2},
		Null,
		leaf(data{3})
	},
	leaf(data{4})
};

The limitations are the same as the list, and nearly no operation is possible at compile-time on all three major compilers.

No parent reference

I know no way to initialize a tree where every node has a reference to its parent, just like I have no idea how to initialize a doubly-linked list. This makes it more difficult to implement certain types of algorithms.

Traversing the tree

There are two main methods for traversing a tree: breadth-first and depth-first.

depth-first traversal is accomplished easily with

template <class F>
void dfs(const node& n, F f){
	f(n);
	if(&(n.left) != &Null){
		dfs(n.left, f);
	}
	if(&(n.right) != &Null){
		dfs(n.right, f);
	}
}

for breadth-first traversal, one needs to define some helper structure, as no node has a reference to its parent.

For creating an iterator-based interface, one needs to define some helper structure where to store all nodes sorted in the right order.

Binary array tree

For most use cases, replacing a tree-like structure with something that wraps an array and provides a tree-like interface would have multiple benefits

better cache locality
smaller data structures
better code reuse (creating iterators both for bfs and dfs is much simpler)
usable in constexpr context with current compilers
if the array size is correct, then it can be interpreted as a valid tree, in the case of node it is possible to create structures that are not trees, as one node could have the root node as children
it is possible to reuse the same data structure for both mutable and immutable trees

The main disadvantage is that if there are multiple data structures with a common subset, it might be harder to remove those duplicates. I do not believe this is an issue for most applications, as replacing the sparse data structure with an array should reduce the size much more, except in rare circumstances.

There is just one (soft) limitation: It is possible to represent a binary tree as an array if this is full.

This means that for a given height h, the tree has $2^{h} - 1$

elements, as there is the following relation

2^{0} + 2^{1} + 2^{2} + ... 2^{n - 1} = \sum_{k = 0}^{n - 1} 2^{k} = 2^{n} - 1

For non-full trees… one has to decide what to do with the gaps in the array. Also if the blacklist has many values, the array will be "sparse", thus another data structure for storing the tree might be better.

bfs traversal

This is trivial, as it is just traversing the tree:

constexpr const int tree[]{
                                0,
                1,                              2,
        3,              4,              5,              6,
    7,      8,      9,      10,     11,     12,     13,    14,
  15,16,  17,18,  19,20,  21,22,  23,24,  25,26,  27,28,  29,30
};

int main(){
	for(const auto& v : tree){
		std::cout << v << ' ';
	}
}

will print 0 1 2 3 4 5 6 7 8 9 ….

dfs traversal

This is trickier but can be done with a helper structure, as one can calculate where the next index is located. This also makes it easier to define a proper iterator

constexpr int children_left(int i) {return i*2+1;};
constexpr int children_right(int i){return i*2+2;};
constexpr int parent(int i)        {return (i-1)/2;};

constexpr int bubble_up(int i, int leaf){
	int k = 1;
	i = parent(i);
	while ((leaf+1) % (k*2) != k ) {
		i = parent(i);
		k*=2;
	}
	return i;
}

struct index_iter{
	int size=-1;
	int i = 0;

	constexpr void next(){
		assert(i != size);
		if(i == size-1){
			i = size;
			return;
		}
		if(i < size/2){
			i = children_left(i);
			return;
		}
		int leaf = i-size/2;
		int tmp_parent = bubble_up(i, leaf);
		i = children_right(tmp_parent);
	}
};

The condition if(i == size-1){i = size;return;} is straightforward. If we are on the last valid element of the array, that means on the last leaf, then the "next" index is one past the end of the array. This is a common convention, also used for iterators, for notifying the user that the new index is invalid.

if(i < size/2){ i = children_left(i); return; } means that as long as we are not on a leaf (as all leaves have index>=size/2), the next element is simply the left children.

The less obvious part is what to do when we are on a leaf which is not the last. If the leaf is the left child of a node, then we can simply go to its brother, but if the leaf is a right node, then we need to got to traverse the tree in the opposite direction, and from a given node select the right children.

How many times we need to traverse parents depends on which node we are. The logic of this procedure is encapsulated in the bubble_up function.

If one manually writes down the number of parents it needs to traverse (even when simply jumping to the brother), it is possible to recognize the following pattern

leaf         0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
bubble steps 1 2 1 3 1 2 1 4 1 2  1  3  1  2  1 ...


Starting from 0 every  2nd element is 1
Starting from 1 every  4th element is 2
Starting from 3 every  8th element is 3
Starting from 7 every 16th element is 4
...
Starting from 2**(k-1)-1 every 2**k th element is k

Thus given a node at index j, one needs to find the value of k for which

2^{k} = j + n \cdot 2^{k - 1} - 1

This is equivalent to testing

j \equiv_{2^{k}} 2^{k - 1} - 1

Determining which leaf we are on simply means subtracting size/2 from the current index. The algorithm then tests all values of k by starting from 1 until it finds one that satisfies the condition. Instead of returning the number of times we need to traverse a parent, it calculates the necessary index directly.

Once index_iter has been declared and implemented, it can be used for implementing an iterator by wrapping it:

struct depthiterator{
	using iterator_category = std::forward_iterator_tag;
	using difference_type   = std::ptrdiff_t;
	using value_type        = const int;
	using pointer           = value_type*;
	using reference         = value_type&;

	index_iter ii;
	std::span<const int> data;

	constexpr depthiterator(std::span<const int> data_) : ii{std::size(data_), 0}, data{data_}{};
	struct end_t{};
	constexpr depthiterator(std::span<const int> data_, end_t) : ii{std::size(data_), std::size(data_)}, data{data_} {};

	constexpr reference operator*() const { return data[ii.i]; }
	constexpr pointer operator->() { return &data[ii.i]; }
	constexpr depthiterator& operator++() {
		ii.next();
		return *this;
	}
	constexpr depthiterator operator++(int) { auto tmp = *this; ++(*this); return tmp; }

	constexpr friend bool operator== (const depthiterator& a, const depthiterator& b) { return a.ii.i == b.ii.i; };
	constexpr friend bool operator!= (const depthiterator& a, const depthiterator& b) { return a.ii.i != b.ii.i; };
};

Which can be used like

int main(){
	for (auto it = depthiterator(tree); it != depthiterator(tree, depthiterator::end_t{}); ++it){
		std::cout << *it << '\n';
	}
	constexpr int i1 = *depthiterator(tree);
	static_assert(i1 == 0, "");
	constexpr int i2 = *(++depthiterator(tree));
	static_assert(i2 == 1, "");
	constexpr int i3 = *(++ ++depthiterator(tree));
	static_assert(i3 == 3, "");
}

and will print 0 1 3 7 15 16 8 17 18 4 … as expected.

There are still improvements that can be made, currently depthiterator does not verify that the size of its input is sensible, as complete trees have a size in the form $2^{n} - 1$ . By providing appropriate abstractions it is possible to turn arrays with unexpected sizes into errors and enable .begin() and .end() functions for both dfs and bfs.

ternary and n-ary node-based trees

Similarly to a binary tree, it is possible to define node for ternary trees:

struct data{int i;};

struct node {
	data d;
	const node& first;
	const node& second;
	const node& third;
};

constexpr const node Null{data{0},Null,Null,Null};

constexpr node leaf(data d){
	return node{d, Null, Null, Null};
}

constexpr const node tree {
	data{1},
	node {
		data{2},
		leaf(data{3}),
		leaf(data{4}),
		leaf(data{5})
	},
	leaf(data{6}),
	leaf(data{7})
};


template <class F>
void dfs(const node& n, F f){
	f(n);
	if(&(n.first) != &Null){
		dfs(n.first, f)
	}
	if(&(n.second) != &Null){
		dfs(n.second, f)
	}
	if(&(n.third) != &Null){
		dfs(n.third, f)
	}
}

But it is annoying that, depending on the number of children, I had to define another node structure.

Thanks to templates it is possible to provide just one definition for all types of trees, but there are a couple of caveats.

#include <array>

namespace detail {
	template <typename T, std::size_t ... Is>
	constexpr std::array<T, sizeof...(Is)> create_array_i(T value, std::index_sequence<Is...>)
	{
		return {{(static_cast<void>(Is), value)...}};
	}
}

template <std::size_t N, typename T>
constexpr std::array<T, N> create_array(const T& value) {
	return detail::create_array_i(value, std::make_index_sequence<N>());
}

struct data{int i;};

template <int N>
struct node;

template <int N>
struct node_ref{
    const node<N>& ref;
};

template <int N>
struct node {
	data d;
	std::array<node_ref<N>, N> children;
};

template <int N, class F>
void dfs(const node<N>& n, F f){
	f(n);
	for(const auto& v : n.children){
		if(&(v.ref) != &Null<N>){
			dfs(v.ref, f);
		}
	}
}

template<int i>
constexpr node<i> Null{data{0}, create_array<i>(node_ref<i>{Null<i>})};

template <int N>
constexpr node<N> leaf(data d){
    return node<N>{d, create_array<N>(node_ref<N>{Null<N>})};
}

constexpr const node<4> tree {
	data{1},
	node<4> {
		data{2},
		leaf<4>(data{3}),
		leaf<4>(data{4}),
		leaf<4>(data{5}),
		leaf<4>(data{6})
	},
	leaf<4>(data{7}),
	leaf<4>(data{8}),
	leaf<4>(data{9}),
};

Something like dfs(tree, [](const node<4>& n){std::cout << n.d.i << '\n';}); will print 1 2 3 4 5 6 7 8 9.

Multiple Null nodes

The first caveat is that the definition of Null depends on a template parameter. In order not to define different constexpr Null values, which would require different names, we need to be able to define a variable template, which requires C++14.

If one still needs to support C++11 it can use a couple of macros to reduce code duplication. Something like the following macros will do the job:

#define define_NullN_constant(j) constexpr const node<j> Null##j{data{0}, create_array<j>(node_ref<j>{Null##j})};
define_NullN_constant(2);
define_NullN_constant(3);
define_NullN_constant(4);
...

template <int N>
constexpr node<N> Null();

#define define_Null_function(j) template<> constexpr node<j> Null(){return Null##j;};
define_Null_function(2)
define_Null_function(3)
define_Null_function(4)
...

Which is not as practical.

Otherwise, for the end-user, it means using Null<j>() instead of Null<j>, i.e. a function instead of a variable.

Array of references

References are not real objects like int, char, float a struct, a pointer, and so on. They are aliases; an alternate name for an object.

While in most cases the difference is not important, in this case, it is. It is not possible to create an array, or std::array, of references.

The fix is simple and consists of a layer of indirection.: struct node_ref. This structure does not seem necessary, and in fact, does not add any functionality or flexibility. But it is possible to create an array of node_ref, while it is not to create an array of const node& or simply node&.

The standard library already provides std::reference_wrapper, but

factory functions like std::cref have a =delete overload for temporaries
it has user-defined constructors
is is only constexpr from C++20

Thus writing down a custom node_ref

makes code easier to write and read/is easier to use
is faster to compile compared to std::reference_wrapper, as it is not necessary to include function
is the same amount of code for providing factory functions like std::cref that accept temporaries
is necessary as std::reference_wrapper would create dangling references

Initialize array with one value

The standard library and C++ language do not provide any mechanism, except default construction and 0-init, for initializing an array with a given value.

In practical terms, it means that creating Null is problematic, as depending on the size the number of arguments changes. This makes both writing a template variable and a macro impossible.

Fortunately, through std::index_sequence, it is possible to write the helper function create_array that creates a std::array with a given value.

ternary and n-ary array tree

Similarly to a binary, tree, a n-ary tree can be trivially mapped to an array if it is full (ie an n-ary tree with height h has $n^{h}$ leaves.)

For example, a ternary tree can be defined in the same way as a binary tree:

constexpr const int tree[]{
          0
  1       2         3
4 5 6   7 8 9   10 11 12
};

As whitespace and formatting are completely irrelevant, the relevant difference is how the data is interpreted/traversed/iterated.

The expected size of the array is

b^{0} + b^{1} + b^{2} + ... + b^{n - 1} = \sum_{k = 0}^{n - 1} b^{k} = \frac{b^{n} - 1}{b - 1}

bfs traversal

Just like a binary tree, bfs traversal is iterating the array, it doesn’t matter if it is a binary, ternary, or another type of tree:

for(const auto& v : tree){
	std::cout << v << ' ';
}

dfs traversal

Similar to a binary tree, when a leaf node is reached, it is necessary to calculate how many parents need to be traversed. Contrary to before, we also need to determine which child we need to traverse, while before we simply selected the right child.

The sequence, this time, for a ternary tree looks like this:

1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 4 ...

but contrary to the sequence of the binary tree, I was not able to write down the pattern as simple rules.

Thus I rechecked the logic of the binary tree and realized that

2^{k} = j + n \cdot 2^{k - 1} - 1

means finding the highest power of 2 that divides 2n (as this check is done only on right leaves).

A similar relation is valid for a ternary tree:

n (leaf+1)   bubble op
 1           -> 1    as 3n == 3*1 ==  3 is divided by 3^1
 2           -> 1    as 3n == 3*2 ==  6 is divided by 3^1
 3           -> 2    as 3n == 3*3 ==  9 is divided by 3^2
 4           -> 1    as 3n == 3*4 == 12 is divided by 3^1
 5           -> 1    as 3n == 3*5 == 15 is divided by 3^1
 6           -> 2    as 3n == 3*6 == 18 is divided by 3^2
 7           -> 1    as 3n == 3*7 == 21 is divided by 3^1
 8           -> 1    as 3n == 3*8 == 24 is divided by 3^1
 9           -> 3    as 3n == 3*9 == 27 is divided by 3^3
10           -> 1    as ...
...

The same relation holds for every n-ary tree (with n>=2).

A naive implementation of such a function is testing with an increasing value if the value we are interested in is divisible or not:

constexpr int highest_pow(int base, int mult){
	int count=0;
	int k = 1;
	while (mult % k == 0 ) {
		k*=base;
		++count;
	}
	return count;
}

There is one last issue: given a parent, how do I know which node to select? If no bubble happened, then it’s the first, but if we just bubbled then I should store somewhere the information on how many nodes I already visited.

Fortunately, there is another way. The information on which nodes have been traversed is available while bubbling up. Thus instead of bubbling up n times, let’s bubble n-1 times and choose the "brother" node.

Put it all together, the algorithm looks like

constexpr int children_left(int base, int i) {return i*base+1;};
constexpr int parent(int base, int i)        {return (i-1)/base;};
constexpr int next_brother(int base, int i)  {(void)base;return i+1;};

constexpr int highest_pow(int base, int mult){
	int count=0;
	int k = 1;
	while (mult % k == 0 ) {
		k*=base;
		++count;
	}
	return count;
}
int bubble_to_parent_min1(int base, int i, int leaf){
	int bubble_op = highest_pow(base, leaf+1);
	for(int j = 0 ; j != bubble_op-1; ++j){
		i = parent(base, i);
	}
	return i;
}
struct index_iter{
	int size;
	int i;
	int base;

	constexpr void next(){
		assert(i != size);
		if(i == size-1){
			i = size;
			return;
		}
		if(i < size/base){
			i = children_left(base, i);
			return;
		}
		int leaf = i-size/base;
		int tmp = bubble_to_parent_min1(base, i, leaf);
		i = next_brother(base, tmp);
	}
};

The class depthiterator can be changed to

struct depthiterator{
	using iterator_category = std::forward_iterator_tag;
	using difference_type   = std::ptrdiff_t;
	using value_type        = const int;
	using pointer           = value_type*;
	using reference         = value_type&;

	index_iter ii;
	std::span<const int> data;

	constexpr depthiterator(std::span<const int> data_, int base) : ii{std::size(data_), 0, base}, data{data_}{
	};
	struct end_t{};
	constexpr depthiterator(std::span<const int> data_, int base, end_t) : ii{std::size(data_), std::size(data_), base}, data{data_} {
	};

	constexpr reference operator*() const { return data[ii.i]; }
	constexpr pointer operator->() { return &data[ii.i]; }
	constexpr depthiterator& operator++() {
		ii.next();
		return *this;
	}
	constexpr depthiterator operator++(int) { auto tmp = *this; ++(*this); return tmp; }

	constexpr friend bool operator== (const depthiterator& a, const depthiterator& b) { return a.ii.i == b.ii.i; };
	constexpr friend bool operator!= (const depthiterator& a, const depthiterator& b) { return a.ii.i != b.ii.i; };
};

and used like

int main(){
	for (auto it = depthiterator(tree, 3); it != depthiterator(tree, 3, depthiterator::end_t{}); ++it){
		std::cout << *it << '\n';
	}
}

thus the output of

constexpr const int tree[]{
                                             0,
              1,                             2,                             3,
    4,        5,        6,         7,        8,        9,        10,       11,       12,
13,14,15, 16,17,18, 19,20,21,  22,23,24, 25,26,27, 28,29,30,  31,32,33, 34,35,36, 37,38,39
};

looks like

0 1 4 13 14 15 5 16 17 18 6 19 20 21 2 7 22 23 24 8 25 26 27 9 28 29 30 3 10 31 32 33 11 34 35 36 12 37 38 39

Non-full n-ary array trees

I’ve written that n-ary trees, if full, can be easily mapped to arrays. But what if the tree is not full?

In this case, a possible approach is having a second array that contains the index of nodes to skip (there is no need to adapt index_iter too).

// for legibility, nodes that should be ignored are written in parenthesis
constexpr const int tree[]{
                                0,
                1,                               2,
        3,               4,              5,                 (6),
    7,       8,      9,      10,     11,     12,     (13),       (14),
 (15),16,  17,18,  19,20,  21,22,  23,24,  25,26,  (27),(28),  (29),(30)
};
constexpr const int tree_blacklist[]{
    15, 6 // NOTE: decrease order for more efficient to_skip/advance function, but output does not depend on it
};

Then, depthiterator should accept an optional blacklist-span for knowing which nodes (and subnodes) to skip.

constexpr bool to_skip(int base, const int i_, std::span<const int> blacklist){
	return std::any_of(blacklist.begin(), blacklist.end(), [&](int b){
		int i = i_;
		while(i > b){
			i = parent(base, i);
		}
		return i == b;
	});
}

constexpr index_iter advance(index_iter ii, std::span<const int> blacklist){
	do{
		ii.next();
	}while(ii.i != ii.size && to_skip(ii.base, ii.i, blacklist));
	return ii;
}

struct depthiterator{
	using iterator_category = std::forward_iterator_tag;
	using difference_type   = std::ptrdiff_t;
	using value_type        = const int;
	using pointer           = value_type*;
	using reference         = value_type&;

	index_iter ii;
	std::span<const int> data;
	std::span<const int> blacklist;

	constexpr depthiterator(std::span<const int> data_, int base, std::span<const int> blacklist_) : ii{std::size(data_), 0, base}, data{data_}, blacklist{blacklist_}{
		ii= advance(ii, blacklist);
	};
	struct end_t{};
	constexpr depthiterator(std::span<const int> data_, int base, end_t) : ii{std::size(data_), std::size(data_), base}, data{data_} {
	};

	constexpr reference operator*() const { return data[ii.i]; }
	constexpr pointer operator->() { return &data[ii.i]; }
	constexpr depthiterator& operator++() {
		ii = advance(ii, blacklist);
		return *this;
	}
	constexpr depthiterator operator++(int) { auto tmp = *this; ++(*this); return tmp; }

	constexpr friend bool operator== (const depthiterator& a, const depthiterator& b) { return a.ii.i == b.ii.i; };
	constexpr friend bool operator!= (const depthiterator& a, const depthiterator& b) { return a.ii.i != b.ii.i; };
};

and can be used like

int main(){
	for (auto it = depthiterator(tree, 2, tree_blacklist); it != depthiterator(tree, 2, depthiterator::end_t{}); ++it){
		std::cout << *it << '\n';
	}
}

In this case, the output will be

1 3 7 16 8 17 18 4 9 19 20 10 21 22 2 5 11 23 24 12 25 26

Notice that also a bfs traversal now requires a custom iterator, and even functions like querying the size require some attention, as it is not the size of the array anymore.

Also, other operations are more complex and error-prone if no adequate abstraction is provided. For example, with a full tree of size N, a node is a leaf if its index i is greater than N/2. If the tree is not full, one needs to check the size and if the elements that are would be it’s children in a full tree are blacklisted or not.

Do you want to share your opinion? Or is there an error, some parts that are not clear enough?

You can contact me anytime.

constexpr tree structures

A node-based binary tree

No parent reference

Traversing the tree

Binary array tree

bfs traversal

dfs traversal

ternary and n-ary node-based trees

Multiple Null nodes

Array of references

Initialize array with one value

ternary and n-ary array tree

bfs traversal

dfs traversal

Non-full n-ary array trees

A `node`-based binary tree