Aight, so the question is about looking for one tree inside another. This is a standard interview problem if the tree has an ordering, but yours doesn't and that makes matters significantly more complicated. Similarly, if we were looking for tree congruence rather than containment, and if we could use Kelly's Theorem as Adam Gent indicates in the OP's comments and just count subtrees.
For clarity's sake, I'm going to call the two trees the pattern tree and the target tree. We want to test whether the pattern tree is a subtree of the target tree.
Your approach is (though I might be understanding) that a node P from the pattern tree is equivalent to a node T in the target tree iff every child of P is equal to a node in T. Thing is, this has a problem: what if P has two identical subtrees as children? It'd match against a node T that only had one subtree!
Now this isn't a fatal flaw: we could adapt this approach by deleting a subtree of T when we think we've found a match, and then doing a pile of backtracking if it later turns out we're wrong. That's kinda prone to combinatorial explosion though.
A better way is to recurse from the ground up rather than the top down. What I mean by this is
- Check whether all the pattern tree's leaves occur in the target tree.
- If they do, build a dictionary D mapping the pattern tree's leaves to lists (there might be more than one!) of matching leaves in the target tree.
- Check whether all height-1 subtrees of the pattern tree occur in the target tree.
- To do this, suppose we have a height-1 node Q from the pattern tree, with leaves X and Y.
- Use the dictionary to get the lists of leaves in the target tree matching X and Y. Filter these lists so that any leaf in the target tree appears at most once (this deals with the case that X is identical to Y)
- See if some leaf matching X in the target tree has a parent in common with a leaf matching Y in the target tree.
- If so, hooray! If this parent is the same type as Q, it's a match! Find all such parents - we'll need them for the next step.
- If all the height-1 subtrees of the pattern tree do indeed appear in the target tree, build a new dictionary mapping them to lists of matching height-1 trees in the target tree.
- Repeat, building a height-2 tree dictionary using the height-1 dictionary.
- Repeat, building a height-3 tree dic- you get the point. Eventually you'll reach the root of the pattern tree and you're done.
This works out at quadratic time, which isn't great but the usual Googling didn't reveal a better algorithm (mostly because the binary tree/ordered tree variants have flooded the search space). If anyone knows of better, I'd be glad to hear it. Using Kelly's Theorem against all subtrees works out at cubic time naively I think, but with some memoization that'd probably come down to quadratic too.