Problem
Two ordered trees T ′ and T ″ are said to be isomorphic if one of the following holds:
• Both T ′ and T ″ are empty
• Both T ′ and T ″ consist of a single node
• Both T ′ and T ″ have the same number k ≥ 1 of sub trees, and the ith sub tree of T ′ is isomorphic to the ith subtree of T ″, for i = 1, ...,k.
Design an algorithm that tests whether two given ordered trees are isomorphic. What is the running time of your algorithm?