Represent a full, but not complete, binary tree with an array structure

Question

I have been reading about binary heaps and I was wondering if there was a similar representation that could be used to represent a non-complete binary tree, if that binary tree happened to also be full.

We can use a sort of arena-allocation to represent any binary tree, using indexes into our memory arena rather than pointers, but the binary heap representation takes advantage of the completeness of the tree to compact the representation. Are there any similar techniques to be employed with a full tree?

Answer 1

One can take advantage of the implied structure of the full binary tree to compress the structure, but it's still O(n) space. This is because the there is distinguishing information in the arrangement that is not there for the complete binary tree: there is, purposefully, just one arrangement.

For example, I've used the fact that a Patrica trie is a full binary tree to represent the structure in a compact (n-1)/2 numbers, where n is nodes, (corresponding to the internal nodes). In my case, I used how many internal nodes are in the sub-tree rooted at the left child. Combined with knowledge of the initial trie size, this allows traversal down the trie. For example, [1,0,0] is reconstructed to a tree with 7 nodes: