If you require the highest performance and your trees are write once, read often (and immutable), it's worth looking into if you should just sort the nodes in traversal order in one contiguous block of memory. Storing the edges as indices into the block is handy in this case.
The article used parent pointers in node to avoid using a stack (native or custom made). One downside of a parent pointer is that your identical subtrees can no longer share structure.
I agree. I would also point out that this doesn't have much advantage (if it has any) over simple recursion, performance wise.
First, the depth (the amount of storage for traversal) typically is on the order of log2(n) and so this gets amortized very quickly when traversing nodes.
What if the tree is unbalanced?
If the tree is unbalanced you will have all sorts of other problems like problems with inserting or searching. Since trees are typically used for efficient searching and traversal is done more efficiently with just plain array (or list) it is really hard to find any real-world trees that are not kept balanced somehow.
Suppose your `Tree` is an array of `Nodes` sorted in whatever traversal order is expected to be good. Edges are fully defined as pairs of indices (Node[A] -> Node[B] means you need to know just A and B): Nodes can contain their own upstream indices.
If you need per-traversal state per node (such as visited status or intermediate dataflow), it's very handy to allocate another flat array for that and use the node indices.
I've looked into this in a compiler setting, transforming ASTs and intermediate representations.
I was confused by that as well before reading the answers: the confusion stemmed from only thinking about the linear traversal or search use cases, where an ordered array plus binary search is all you'd ever need for reading. But when the tree shape itself is still needed, indices can be better than pointers, particularly when adding sidecar arrays for extension or as temporary scribble space (see sibling comment).
Hurting because of memory alignment or something else?
Given we have indices along the serialisation for child nodes I would have thought not having nodes start at the consistent intervals doesn't hurt us for traversal at least.
I'd quite like to use this idea for a file backed immutable tree. The array of children would have variable size with bit field to index then nth child in the sparse array.
Constant time array indexing depends on a fixed array member size. So, the actual memory layout of storing the nodes with non-fixed size could not use an array of nodes.
I suppose you could (should) write your own allocator to ensure nodes are allocated in a contiguous piece of memory, and have a separate array of indexes / pointers that tells you where the n-th node starts. That is another array that'll have to be kept in cache though.
The article used parent pointers in node to avoid using a stack (native or custom made). One downside of a parent pointer is that your identical subtrees can no longer share structure.