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.
This is super relevant to me right now, thanks!
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.
[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.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.
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.