# Solving a "tree-equation"?

Given two trees A and B, each of their nodes except some leaves have a "type" (which also determines the number of children, the node has, having that type). The leaves which don't have a type are identified by letters (variables) (a,b,c,...). Each letter may occur multiple times in a tree.

The task is to devise an algorithm to 'solve' the 'equation' A=B, i.e. assign trees to the variables (possibly containing other variables). One tree (x) equals to an other (y) iff x and y are the same variables or the root of both have the same type and their respective children are equal.

In the following the "types" are numbers.

Example 1:

A tree is

1
|-2
|-a


B tree is

1
|-2
|-3


The solution is a->3

Example 2:

A tree is

1
|-2
|-a


B tree is

1
|-3
|-3


This does not have a solution.

Example 3:

A tree is

1
|-2
|-a


B tree is

1
|-2
|-b


The solution is a=b (the equation is underdetermined so to say)

• From your post it seems that the trees are rooted {i.e root 1 with child 2 and root 2 with child 1 are considered different trees} and that children are ordered {i.e that root 1 with children 2 and 3 and root 1 with children 3 and 2 are considered different}, please confirm. May 20, 2017 at 13:01
• @daniello indeed that is true.
May 20, 2017 at 13:39
• In that case just doing a DFS in both trees simultaneously should do the trick, no? May 20, 2017 at 15:04
• Isn't this just en.wikipedia.org/wiki/Unification_(computer_science) ? May 20, 2017 at 21:35
• @DavidEppstein looks like exactly what i was looking for