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))
Best Answer
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).