I have the following 2 trees.
Tree 1 with branches from br_a to br_i and a root point.
Tree 2 with branches from br_a to br_c and a root point.
Each vertex/node in this tree has a position (x, y), and all edges have the same weight. I would like to perform a bipartite matching between the branches of Tree 1 and Tree 2, such that we obtain a sub tree of Tree 1 that best matches the Tree 2. So, if we match a Tree 1 branch to a Tree 2 branch then we must also match all the parent branches of the Tree 1 matched branch (up till the root point) to the parent branches of the Tree 2 matched branch. In the given example, the following sub tree of Tree 1 would be the best match because of the most similar topology and position of the nodes.
How can I do this? Is there any tree matching algorithm for this kind of matching. One naive way of matching that I can think of is to create all possible sub tree permutations. For example,
Then match each of the sub tree to Tree 2, one by one, and pick the one with best match. Here my question is what algorithm can I use to match these trees that incorporates the position of the nodes as a matching criteria. Any help or pointers would be appreciated.