3
$\begingroup$

I want to compare two trees: I will consider the trees equal if they are:
Isomeric-i.e have the same structure.
Nodes in both trees have the same values but the order of the children nodes are not necessarily the same.
A picture is worth a thousand words: eg:

A)                B)              C)                D) 
    (2)                (2)               (2)                  (2)
  /  |  \            /  |  \           /  |  \              /  |  \
(4) (5) (7)        (5) (7) (4)       (5) (4) (7)          (5) (4) (7)
 |   |              |       |         |   |                |   |
(3) (7)            (7)     (3)       (7) (3)              (3) (7)
    / \            / \               / \                      / \
   (0) (1)       (1) (0)           (0) (1)                  (0) (1)

Trees A), B) and C) are equal.
Tree D) isnt equal to any of the trees due to subtrees:
(5) and  (4)
 |        |
(3)      (7)
         / \
       (0) (1)

I have already looked at the classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman but his algo only checks for structure but doesnt account for contents/values in the respctive nodes. link

I was wondering if its possible to incomporate the comparison of the actual node values into this algorithm?

A trivial algorithm will be to sort children nodes for all nodes seriallize the resulting tree for both trees then a simple comparison might suffice.

I was wondering if there exist a more eficient way of accomplishing this.

Update: NODE values are not distinct and could be repetive.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ (In addition to the answer, just in case you miss the following point) In related problems, isomorphism complicates things exactly because the labels in the graphs can be different. When the labels must match, the problem is just to check that the graphs are exactly the same (i.e. have the same adjacency matrix), which is trivial. In particular, Graph isomorphism, currently not known to be in P, becomes trivial with the additional requirement that the labels must match. $\endgroup$
    – Dmitry
    Commented Dec 20, 2022 at 0:02
  • 1
    $\begingroup$ @Dmitry that answer assumes that the node values are distinct. What if the node values could be repetitive? $\endgroup$
    – African_king
    Commented Dec 20, 2022 at 15:53
  • 1
    $\begingroup$ I see, I missed that. Then you should just modify the Aho's algorithm. The modification is trivial: if $\ell$ is the node's label and $x$ is the node's number generated by the algorithm, then in the algorithm, instead of $x$ use tuple $(x,\ell)$ for comparisons (compere tuples lexicographically). $\endgroup$
    – Dmitry
    Commented Dec 20, 2022 at 16:18
  • $\begingroup$ @Dmitry will this affect the time complexity signinficantly. I know originally Aho's algo can me optimized to linear time complexity. Would that be possible when i include this modification? $\endgroup$
    – African_king
    Commented Dec 20, 2022 at 17:48
  • 1
    $\begingroup$ It'll take $O(n \log n)$ time due to sorting (their algorithm also uses sorting, but it can be done in linear time using counting sort). The main subproblem to solve is "given two arrays, do they have the same elements?". For this subproblem, I suspect that $\Omega(n \log n)$ is theoretically required. In practice, you can get $O(n)$ with hashmaps. $\endgroup$
    – Dmitry
    Commented Dec 20, 2022 at 18:11

1 Answer 1

Reset to default
8
$\begingroup$

It's much simpler than isomorphism.

For each vertex, check that the parent is the same in both trees.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Pretty amazing what a difference the labels make! $\endgroup$
    – Matt Groff
    Commented Dec 20, 2022 at 4:17
  • $\begingroup$ Yes, with labels, it's not even isomorphism, it's actually checking equivalence. $\endgroup$
    – John Kemeny
    Commented Dec 20, 2022 at 9:42
  • $\begingroup$ This assumes each value only appears once? $\endgroup$
    – justhalf
    Commented Dec 20, 2022 at 10:31
  • $\begingroup$ Well, yes, otherwise it's just tree isomorphism again. If every vertex can be labelled 1. I assumed, since OP had labelled the $n$ nodes from $1,...,n$ that they were unique. Maybe I'm mistaken. $\endgroup$
    – John Kemeny
    Commented Dec 20, 2022 at 10:50
  • 2
    $\begingroup$ This does not work when identical values are allowed. "the same" turns to "the sames". $\endgroup$
    – user16034
    Commented Dec 20, 2022 at 15:58

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.