# How to determine whether two trees (not necessarily binary) are isomorphic

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))
``````
• 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. 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