3
$\begingroup$

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)

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – daniello
    May 20, 2017 at 13:01
  • $\begingroup$ @daniello indeed that is true. $\endgroup$
    – Adam
    May 20, 2017 at 13:39
  • $\begingroup$ In that case just doing a DFS in both trees simultaneously should do the trick, no? $\endgroup$
    – daniello
    May 20, 2017 at 15:04
  • 4
    $\begingroup$ Isn't this just en.wikipedia.org/wiki/Unification_(computer_science) ? $\endgroup$ May 20, 2017 at 21:35
  • $\begingroup$ @DavidEppstein looks like exactly what i was looking for $\endgroup$
    – Adam
    May 21, 2017 at 6:51

1 Answer 1

9
$\begingroup$

The process you seem to be looking for (merging two descriptions of labeled trees) is called unification. According to the linked Wikipedia article it can be solved in linear time.

$\endgroup$
1
  • 3
    $\begingroup$ For an extensive and understandable presentation of unification and its related algorithms, I would recommend the famous "All that" book : Franz Baader and Tobias Nipkow (1998). Term Rewriting and All That. Cambridge University Press. $\endgroup$
    – holf
    May 22, 2017 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.