# Finding similar subtree structures.

This topic is 4956 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Let's say I have some arbitrary tree of varying degree. If a particular node is selected, it's the root of some subtree. I'm interested in looking through the rest of the whole tree to find any subtrees of similar structure. That is, if the selected node were to be a leaf, the method would return an array of all nodes that are leafs. Again, the content of the nodes is not important; only the structure of the subtree that a particular node is the root of. My first solution is to create a new tree of identical structure of the subtree underneath the selected node. Then, traverse the whole tree, comparing the subtree created by every node by marking that node, then moving through the separate subtree to the tree created by the node. However, this is extremely inefficient considering the amount of repeated traversing. Any ideas on how to make this cleaner/more efficient? --Vic--

##### Share on other sites
It's a tricky problem to solve well. It's known as the "subtree isomorphism problem". Google search for this term should turn up lots of resources.

##### Share on other sites
Thanks. Terminology's always one of my weakest areas. Should have guessed there was a term for it. Time to research!

--Vic--

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• ### Forum Statistics

• Total Topics
633385
• Total Posts
3011605
• ### Who's Online (See full list)

There are no registered users currently online

×