Background

For context, see my previous post about defining nodes and why I’m doing this.

Basic Tree Operations

In the previous post we defined our basic node structure and now we will use the nodes to build a tree.

For this tree I wanted to define some basic constraints that will influence my design.

1. The tree must own all of its own allocations. This will make more sense when we talk about how Zig manages heap memory.
2. Formally we are building an arborescence where m=2 and each node is unique, but informally this is a binary tree that will be unbalanced yet sorted.
3. Duplicate values cannot be inserted into the tree.

If we remember the node implementation, each node has a left_child and a right_child that are optional pointers to other nodes. This means the linked structure of our tree with a depth of 3 would look like this.