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).

You add integer slots to each node and store the index of the child nodes in them. So you have, for a binary tree,

  [actualTreeNodeData1,child1Idx,child2Idx][actualTreeNodeData2,child1Idx,child2Idx][...]

instead of just

  [actualTreeNodeData1][actualTreeNodeData2][...]

Vary this to include whatever you actually need, could also be links to parents instead of or in addition to links to child nodes.

That feels like it'll start hurting when you don't know the (maximum) degree of your nodes. As you won't have fixed-size object anymore.

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.

Typically you'd have a handful in-object and a heap allocated tail if needed. A bit like small string optimization.