Reconstructing trees from a “fingerprint”

Question

I've done my SO and Google research, and haven't found anyone who has tackled this before, or at least, anyone who has written about it.

My question is, given a "universal" tree of arbitrary height, with each node able to have an arbitrary number of branches, is there a way to uniquely (and efficiently) "fingerprint" arbitrary sub-trees starting from the "universal" tree's root, such that given the universal tree and a tree's fingerprint, I can reconstruct the original tree?

For instance, I have a "universal" tree (forgive my poor illustrations), representing my universe of possibilities:

                Root
        /  /  /  |  \  \ ... \
       O  O  O   O   O  O     O  (Level 1)
      /|\/|\...................\ (Level 2)

etc.

I also have tree A, a rooted subtree of my universe

        Root
      / /|\ \
     O O O O O
    /

Etc.

Is there a way to "fingerprint" the tree, so that given that fingerprint, and the universal tree, I could reconstruct A?

I'm thinking something along the lines of a hash, a compression, or perhaps a functional/declarative construction? Big-O analysis (in time or space) is a plus.

As a for-instance, a nested expression like: {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...} representing the actual nodes present at each level in the tree is probably valid, but can it be done more efficiently?

Answer 1

I would use a list of lists, where each element in the list states how many children you have:

[[2][1,2][0,0,0]]

Is a tree with two nodes on the first level and the left child has one child node, and the right child node has 2 of its own.

Run that output through a lossless compression algorithm of your choice.

You could also use a depth-first traversal of the tree, or any other type of traversal really. Whatever is easiest for you to reconstruct from.