# Efficient way to find max height repetitive sub-trees in an object tree

I am trying to solve a problem of finding a max repetitive sub-tree in an object tree.

By the object tree I mean a tree where each leaf and node has a name. Each leaf has a type and a value of that type associated with that leaf. Each node has a set of leaves / nodes in certain order.

Given an arbitrary object tree that - we know - has a repetitive sub-tree in it.

By repetitive I mean 2 or more sub-trees that are similar in everything (names/types/order of sub-elements) but the values of leaves. No nodes/leaves can be shared between sub-trees.

Problem is to identify these sub-trees of the max height.

I know that the exhaustive search can do the trick. I am rather looking for more efficient approach.

For each non-leaf node in the tree make a hash of its names/order and of the hashes of its ordered sub-nodes. If a node is a leaf then its hash is its name/type. This gives an O(N) algorithm to get all the heights and subtree hashes. Next you can traverse the tree in order of decreasing height until you find a hash that matches one you've seen earlier -- this is your target match. So the whole algorithm is O(N).

• Nice, that should work. I am not marking it as answered hoping to get more ideas. Sep 4, 2012 at 17:51
• I'd mark this as answered. Hashing is pretty clearly the optimal choice. Are there any particular qualities you'd like out of a different algorithm? Sep 5, 2012 at 1:22
• @GeoffreyIrving, done. Yes I do, but the problem is put slightly differently and a hash wouldn't really work there. Let me explain. What I really need is not a 100% match (where a hash would work perfectly), but to find a max sub-set of elements 2 different nodes have in common. To avoid the specifics, I have a comparison function that for 2 given nodes gets a number from 0 to 1 which represent the similarity between 2 nodes. The implementation of that function is unknown. Nodes are considered similar if this number is over some threshold. Sep 12, 2012 at 14:28
• If the details of the comparison function are unknown, I believe there's no way to beat quadratic time in the number of trees. Sep 12, 2012 at 16:27