# Check if Tree is Isomorphic

In this article, we are going to see how to check a tree whether isomorphic or not? This problem has been featured in interview coding round of Microsoft, Amazon.
Submitted by Radib Kar, on February 04, 2019

Problem statement:

Write a function to detect if two trees are isomorphic. Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped.

Example1: These two trees are isomorphic

Swap left child & right child of 1 Swap left & right child of 5 Example 2: Solution:

The conditions which needed to be satisfied are:

1. Empty trees are isomorphic
2. Roots must be the same
3. Either left subtree & right subtree of one must be same with the same of other's, or left subtree of one must been same with right subtree of other's & right subtree of one must same with left subtree of other's.

Pre-requisite:

Two Input binary trees (their roots actually), i.e., root1, root2

```FUNCTION isIsomorphic(Node *root1,Node *root2)
1.  Both are empty then it's isomorphic. //condition-1
IF (!root1 && !root2)
return true;
If particularly exactly one of them is empty,
then they can't be isomorphic.//extension of condition-1
IF(!root1 || !root2)
return false;
2.  If root value are different, they can't be isomorphic//condition-2
IF(root1->data!=root2->data)
return false;
3.  Check condition-3
Recursively checking subtrees
return ( (  isIsomorphic(root1->left,root2->left) &&
isIsomorphic(root1->right,root2->right) ) ||
(isIsomorphic(root1->right,root2->left) &&
isIsomorphic(root1->left,root2->right)));
END FUNCTION
```

C++ implementation

```#include <bits/stdc++.h>
using namespace std;

// TreeNode node type
class TreeNode{
public:
int val;           //value
TreeNode *left;    //pointer to left child
TreeNode *right;   //pointer to right child
};

// creating new node
TreeNode* newnode(int data)
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = data;
node->left = NULL;
node->right = NULL;

return(node);
}

// function to check isomorphic trees
bool isIsomorphic(TreeNode *root1,TreeNode *root2)
{
if(!root1 && !root2)
return true;

if(!root1 || !root2)
return false;

if(root1->val!=root2->val)
return false;

return ( (isIsomorphic(root1->left,root2->left) &&
isIsomorphic(root1->right,root2->right) )||
(isIsomorphic(root1->right,root2->left) &&
isIsomorphic(root1->left,root2->right)));
}

int main(){
cout<<"tree is built as per example-1\n";

TreeNode *root1=newnode(1);
root1->left= newnode(5);
root1->right= newnode(2);
root1->right->right=newnode(3);
root1->left->left=newnode(8);
root1->left->right=newnode(4);

TreeNode *root2=newnode(1);
root2->left= newnode(2);
root2->right= newnode(5);
root2->right->right=newnode(8);
root2->right->left=newnode(4);
root2->left->right=newnode(3);

if(isIsomorphic(root1,root2))
cout<<"They are isomorphic tree\n";
else
cout<<"They are not isomorphic tree\n";

cout<<"tree is built as per example-2\n";

TreeNode *root3=newnode(1);
root3->left= newnode(9);
root3->right= newnode(2);
root3->right->right=newnode(3);
root3->left->left=newnode(8);
root3->left->right=newnode(4);

if(isIsomorphic(root1,root3))
cout<<"They are isomorphic tree\n";
else
cout<<"They are not isomorphic tree\n";

return 0;
}
```

Output

```tree is built as per example-1
They are isomorphic tree
tree is built as per example-2
They are not isomorphic tree
```

Explanation with example

Let's check the example-1

Nodes are represented by their respective values for better understanding

```In the main we call isIsomorphic(root1,root2) //isIsomorphic(1,1)
------------------------------------------------

isIsomorphic(1,1)
root1 is not NULL
root2 is not NULL
root1->data==root2->data
thus it returns
((isIsomorphic(root1->left,root2->left) && isIsomorphic(root1->right,root2->right)) ||
(isIsomorphic(root1->right,root2->left) && isIsomorphic(root1->left,root2->right)));
i.e.,
((isIsomorphic(5,2) && isIsomorphic(2,5)) ||
(isIsomorphic(2,2) && isIsomorphic(5,5)));

Thus call to isIsomorphic(5,2), isIsomorphic(2,5),
isIsomorphic(2,2), isIsomorphic(5,5)
------------------------------------------------

isIsomorphic(5,2)
root1 is not NULL
root2 is not NULL
root1->data!=root2->data
thus it returns FALSE
------------------------------------------------

isIsomorphic(2,5)
root1 is not NULL
root2 is not NULL
root1->data!=root2->data
thus it returns FALSE
------------------------------------------------

isIsomorphic(2,2)
root1 is not NULL
root2 is not NULL
root1->data==root2->data
thus it returns
((isIsomorphic(root1->left,root2->left) && isIsomorphic(root1->right,root2->right) ) ||
(isIsomorphic(root1->right,root2->left) && isIsomorphic(root1->left,root2->right)));
i.e.,
((isIsomorphic(NULL,NULL) && isIsomorphic(3,3)) ||
(isIsomorphic(3,NULL) && isIsomorphic(NULL,3)));

Thus call to isIsomorphic(NULL,NULL), isIsomorphic(3,3),
isIsomorphic(3,NULL), isIsomorphic(NULL,3)
------------------------------------------------

isIsomorphic(NULL,NULL)
root1 is NULL
root2 is NULL
thus it return TRUE
------------------------------------------------

isIsomorphic(3,3)
root1 is not NULL
root2 is not NULL
root1->data==root2->data
thus it returns
((isIsomorphic(root1->left,root2->left) && isIsomorphic(root1->right,root2->right) ) ||
(isIsomorphic(root1->right,root2->left) && isIsomorphic(root1->left,root2->right)));
i.e.,
((isIsomorphic(NULL,NULL) && (isIsomorphic(NULL,NULL) ||
(isIsomorphic(NULL,NULL) && (isIsomorphic(NULL,NULL)));

Thus call to isIsomorphic(NULL,NULL), (isIsomorphic(NULL,NULL),
(isIsomorphic(NULL,NULL), (isIsomorphic(NULL,NULL))

All (isIsomorphic(NULL,NULL) returns TRUE
Thus, isIsomorphic(3,3) returns TRUE
------------------------------------------------

isIsomorphic(3,NULL)
exactly one root is empty
Thus it returns FALSE
------------------------------------------------

isIsomorphic(NULL,3)
exactly one root is empty
Thus it returns FALSE

------------------------------------------------

Thus ,
isIsomorphic(2,2)
=((isIsomorphic(NULL,NULL) && isIsomorphic(3,3) ) ||
(isIsomorphic(3,NULL) && isIsomorphic(NULL,3)))
=(TRUE && TRUE)|| (FALSE && FALSE)
=TRUE && FLASE
=TRUE

Same way, we can check that isIsomorphic(5,5) returns TRUE
------------------------------------------------

At main:
isIsomorphic(1,1)
=((isIsomorphic(5,2) && isIsomorphic(2,5)) ||
(isIsomorphic(2,2) && isIsomorphic(5,5)))
=((FALSE && FALSE)||(TRUE && TRUE)
=(FALSE && TRUE)
TRUE

Thus these two trees are isomorphic.
```

You can check the second example same way & can find returning FALSE

TOP Interview Coding Problems/Challenges

Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.