I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number of vertices is less than 20) and degree is upper bounded by 4, such that we can reconstruct the tree form the encoding, decoding is not necessary to be unique but low degeneracy is expected. Currently, I am given the number of vertices at various distance from the root, say $d = [d_1, d_2, ..., d_k]$ where $d_i$ is the number of vertices at distance $i$ from root. However, the number of tree satisfying this condition is very large. I am looking for other representation (as an alternative to $d$) of tree which will be more suitable for reconstruction, may be approximately. I would prefer the representation which is hierarchical in the sense that, first few information are more constrained and informative, and others are gradually less so. For example, here $d_1$ gives complete information on number of nodes at level 1, there is slight degeneracy in constructing level two nodes from $d_2$, etc. My focus is on approximate reconstruction rather than canonical encoding.
I'm still not sure that I completely understand the problem domain, but here's a few suggestions:
- The depth of each leaf.
- The difference between min and max number of children at each depth.
- The number of leaves below each node.
- The difference between the depths of the left and right subtrees for an in-order traversal.
- The weights required to build a Huffman tree of the same structure.