0

Two ordered trees T' and T'' are said to be isomorphic if one of the following holds:

◦ both T' and T'' consist of a single node

◦ both T' and T'' have the same number k of subtrees, and the ith subtree of T' is isomorphic to the ith subtree of T'', for i = 1, 2, ..., k.

I've made an attempt to come up with the following algorithm for binary trees, however the question does not say anything about the tree being binary. What kind of algorithm could determine if two non-binary trees are isomorphic or not?

bool isomorphic(node p, node r)
     if (p = null & r = null) return true
     if (p = null || r = null) return false //they don’t have the same number of subtrees
     else return (isomorphic(p->leftchild, r->leftchild) && isomorphic(p->rightchild, r->rightchild) || (isomorphic(p->leftchild, r->rightchild) && isomorphic(p->rightchild, r->leftchild))
2
  • 4
    Just extend your algorithm to visit the two sequences of children and determine whether each two children at the same position are isomorphic. As an alternative, you can represent arbitrary trees using binary trees: use the right child as a pointer to the list of a node's siblings, and the left child as a pointer to the list of a node's children. In the second case, arbitrary-tree isomorphism is reduced to binary-tree isomorphism.
    – Giorgio
    Commented Mar 10, 2015 at 6:34
  • Your definition almost reads as an algorithm already -- just check those things and use recursion to find out of the subtrees are isomorphic. Commented Apr 9, 2015 at 8:13

1 Answer 1

1

What Giorgio said. Just change the function so that it iterates over a list of children instead of checking only a left and a right child (assuming that's how the non-binary tree you're interested in is implemented).

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.