> There must be existing uses of this encoding, but I’ve been unable to find any or even determine what its name is.<p>not a tree guru.. but isn't this somewhat related to 'fractal tree indexing':<p><a href="https://en.wikipedia.org/wiki/Fractal_tree_index" rel="nofollow">https://en.wikipedia.org/wiki/Fractal_tree_index</a><p><pre><code> Each internal node of a B-tree will contain a number of keys that is
one less than its branching factor. The keys act as separation values
which divide its subtrees. Keys in subtrees are stored in search tree order,
that is, all keys in a subtree are between the two bracketing values.
In this regard, they are just like B-trees.
</code></pre>
also, thanks for the plan9 stuff :D
I like using a level-order traversal because it makes your indexing very simple. For a binary tree you start with 1 and each node has children 2 * i and 2 * i + 1, and parent i / 2. You can do a inorder/preorder/postorder traversal using the typical methods, but for a level-order traversal all you need to do is walk through the backing array.<p>This also generalizes to k-trees. Start at node k-1. your children are ((i - k + 2) * k) through ((i - k + 2) * k) + (k - 1), and your parent is ((i / k) - 2 + k) with integer division. Once again this all fits nicely into a flat backing array and requires no extra memory to store children or parents.