find a node of a tree in another tree

Question

My problem is: Consider two trees P and R. I need to match the node at the deepest possible level of P with the node at deepest possible level of tree R. That means, all nodes in a tree are like a hierarchical relation from most general to most specific. The most specific match from tree P with tree R should be found. The most optimal method is needed.

For example, lets have a Reviewers' panel. Each reviewer has his own tree of interests going from general interest to specific like from Energy to Biogas plant. Now there's a paper to be matched with the reviewer's interests. The reviewer with the most specific match with the paper's category is to be found. Each paper also has its category tree from most general category to exactly specific category.

Answer 1

EDIT: Fixed expression for depth difference

1. Decide how much importance you want to give to matching nodes on their depth, versus on their "similarity". Use this to make a scoring function s(x, y) = a*(-|depth(x) - depth(y)|) + (1-a)*(similarity(x, y)). (similarity(x, y) can be any function of x and y -- e.g. it might be the length of their longest common subsequence, if x and y are strings.)
2. (Conceptually) create a vertex for each node in tree 1, a vertex for each node in tree 2, and an edge for every pair of vertices (x, y) with x in the first tree and y in the second. Set the weight of this edge to s(x, y).
3. You now have a bipartite maximum weighted matching problem, a.k.a. Assignment Problem. Apply the Hungarian algorithm to find the optimal solution in O(n^3) time.

Answer 2

You can solve it using Trie, where the root has the most generalized categories and its children has more specific categories and their children have more and more specific. You need to find the longest matching starting from the root.