Tree matching using serialization of tree and unique id generation for each subtree.

Answer 1

Do you want to to be able match any arbitrary part of the tree or a subtree running upto some leaf node(s)? IIUC, you are looking at suffix matching.

You can also look at Compact Directed Acyclic Word Graph for ideas.

Answer 2

If you're not looking for high efficiency, you might want to use a very simple depth-first-search algorithm.

"2,7,2,U,6,5,U,11,U,U,U,5,9,4"

As you can see, i added U commands ("up") so as to show where the next child would be created. Of course you can make this more efficient, but i believe that's a start.

Also, you might want to have a look at Boost.Graph (BGL) for implementation.

Answer 3

What's wrong with the parentheses notation like you used in your question?

Answer 4

I would make a hash value (in some Rabin-Karp fashion) based on the nodes' IDs and position in the tree, ie:

long h = 0
for each node in sub tree:
    h ^= node.id << (node.depth % 30)

in pseudo code. The downside is that different subtrees may yield the same hash value. But the advantage is that it is fast to compare hash values, and when match is found you can further investige the actual sub tree for equality.