EDIT: Fixed expression for depth difference
- 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.)
- (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).
- 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.