Two ordered trees T and T are said to be isomorphic if one o

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, ..., k. Design an algorithm that tests whether two given ordered trees are isomorphic. What is the running time of your algorithm?

Solution

#include <iostream>
using namespace std;

struct node
{
int data;
struct node* left;
struct node* right;
};

bool isIsomorphic(node* n1, node *n2)
{

if (n1 == NULL && n2 == NULL)
return true;


if (n1 == NULL || n2 == NULL)
return false;

if (n1->data != n2->data)
return false;

return
(isIsomorphic(n1->left,n2->left) && isIsomorphic(n1->right,n2->right))||
(isIsomorphic(n1->left,n2->right) && isIsomorphic(n1->right,n2->left));
}

node* newNode(int data)
{
node* temp = new node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;

return (temp);
}

int main()
{
struct node *n1 = newNode(4);
n1->left = newNode(2);
n1->right = newNode(3);
n1->left->left = newNode(4);
n1->left->right = newNode(10);
n1->right->left = newNode(13);
n1->left->right->left = newNode(7);
n1->left->right->right = newNode(8);

struct node *n2 = newNode(4);
n2->left = newNode(3);
n2->right = newNode(2);
n2->right->left = newNode(4);
n2->right->right = newNode(10);
n2->left->right = newNode(13);
n2->right->right->left = newNode(8);
n2->right->right->right = newNode(7);

if (isIsomorphic(n1, n2) == true)
cout << \"Yes\";
else
cout << \"No\";

return 0;
}
The time complexity of this algorithm is O(m+n) here m and n are number of nodes in the tree.