How do I find a matching subtree?

Question

I have a large binary tree, T. T "matches". Some number of subtrees of T will also match. In fact, the matching subtrees need not even be full subtrees: they can be truncated, too. By truncated subtree, I mean that nodes in the subtree may not contain children all the way down - some nodes that have children may have their children removed.

An example: see this link. The tree represented by poem1, stanza1, stanza2, line3 is an example of a truncated subtree.

Determining if a tree matches requires performing a calculation on that entire tree. It's not progressive.

How the heck do I find all matches?

Answer 1

http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

sounds roughly like what you're trying to find (except that you're trying this on all subgraphs of an original graph as well, making it even harder). I don't really know how you are defining "matches" (equality, pattern, color coordinated, sticks with chemicals on the end that ignite when struck?), so it might be quite a different problem.