Reconstructing trees from a "fingerprint"
- by awshepard
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?
