Check if two trees are isomorphic or not
Two trees are isomorphic when tree node arrangement are mirror form. Our goal is to check given two trees are isomorphic or not. Example of isomorphic tree.
isomorphic tree is depend node values and depend on tree structure. Let see an example of non isomorphic trees.
Here given code implementation process.
/*
C program for
Check if two trees are isomorphic
*/
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create dynamic node
struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode *newNode(int data)
{
// Create dynamic node
struct TreeNode *new_node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates,
// segmentation fault or memory overflow problem
printf("Memory Overflow\n");
exit(0);
}
//return new node
return new_node;
}
int isIsomorphic(struct TreeNode *t1, struct TreeNode *t2)
{
if (t1 == NULL && t2 == NULL)
{
// When both t1 and t2 is null
return 1;
}
if ((t1 == NULL || t2 == NULL) || (t1->data != t2->data))
{
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return 0;
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return (isIsomorphic(t1->left, t2->left) && isIsomorphic(t1->right, t2->right)) || (isIsomorphic(t1->left, t2->right) && isIsomorphic(t1->right, t2->left));
}
int main(int argc, char
const *argv[])
{
struct BinaryTree *tree1 = newTree();
struct BinaryTree *tree2 = newTree();
struct BinaryTree *tree3 = newTree();
struct BinaryTree *tree4 = newTree();
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
tree1->root = newNode(1);
tree1->root->left = newNode(2);
tree1->root->right = newNode(7);
tree1->root->right->right = newNode(8);
tree1->root->left->right = newNode(3);
tree1->root->left->left = newNode(6);
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
tree2->root = newNode(1);
tree2->root->left = newNode(7);
tree2->root->right = newNode(2);
tree2->root->right->right = newNode(6);
tree2->root->right->left = newNode(3);
tree2->root->left->left = newNode(8);
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
tree3->root = newNode(1);
tree3->root->left = newNode(7);
tree3->root->right = newNode(9);
tree3->root->right->right = newNode(6);
tree3->root->right->left = newNode(3);
tree3->root->left->left = newNode(8);
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
tree4->root = newNode(1);
tree4->root->left = newNode(2);
tree4->root->right = newNode(7);
tree4->root->right->right = newNode(8);
tree4->root->left->right = newNode(3);
tree4->root->left->left = newNode(6);
if (isIsomorphic(tree1->root, tree2->root) == 1)
{
printf("\n Tree1 and Tree2 is isomorphic");
}
else
{
printf("\n Tree1 and Tree2 is not isomorphic");
}
if (isIsomorphic(tree1->root, tree3->root) == 1)
{
printf("\n Tree1 and Tree3 is isomorphic");
}
else
{
printf("\n Tree1 and Tree3 is not isomorphic");
}
if (isIsomorphic(tree2->root, tree4->root) == 1)
{
printf("\n Tree2 and Tree4 is isomorphic");
}
else
{
printf("\n Tree2 and Tree4 is not isomorphic");
}
return 0;
}Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic/*
Java program for
Check if two trees are isomorphic
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public boolean isIsomorphic(TreeNode t1, TreeNode t2)
{
if (t1 == null && t2 == null)
{
// When both t1 and t2 is null
return true;
}
if ((t1 == null || t2 == null) || (t1.data != t2.data))
{
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return false;
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return (isIsomorphic(t1.left, t2.left) &&
isIsomorphic(t1.right, t2.right)) ||
(isIsomorphic(t1.left, t2.right) &&
isIsomorphic(t1.right, t2.left));
}
public static void main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
BinaryTree tree3 = new BinaryTree();
BinaryTree tree4 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(8);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.left = new TreeNode(6);
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(7);
tree2.root.right = new TreeNode(2);
tree2.root.right.right = new TreeNode(6);
tree2.root.right.left = new TreeNode(3);
tree2.root.left.left = new TreeNode(8);
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
tree3.root = new TreeNode(1);
tree3.root.left = new TreeNode(7);
tree3.root.right = new TreeNode(9);
tree3.root.right.right = new TreeNode(6);
tree3.root.right.left = new TreeNode(3);
tree3.root.left.left = new TreeNode(8);
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
tree4.root = new TreeNode(1);
tree4.root.left = new TreeNode(2);
tree4.root.right = new TreeNode(7);
tree4.root.right.right = new TreeNode(8);
tree4.root.left.right = new TreeNode(3);
tree4.root.left.left = new TreeNode(6);
if (tree1.isIsomorphic(tree1.root, tree2.root))
{
System.out.print("\n Tree1 and Tree2 is isomorphic");
}
else
{
System.out.print("\n Tree1 and Tree2 is not isomorphic");
}
if (tree1.isIsomorphic(tree1.root, tree3.root))
{
System.out.print("\n Tree1 and Tree3 is isomorphic");
}
else
{
System.out.print("\n Tree1 and Tree3 is not isomorphic");
}
if (tree2.isIsomorphic(tree2.root, tree4.root))
{
System.out.print("\n Tree2 and Tree4 is isomorphic");
}
else
{
System.out.print("\n Tree2 and Tree4 is not isomorphic");
}
}
}Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Check if two trees are isomorphic
*/
// Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public:
TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
bool isIsomorphic(TreeNode *t1, TreeNode *t2)
{
if (t1 == NULL && t2 == NULL)
{
// When both t1 and t2 is null
return true;
}
if ((t1 == NULL || t2 == NULL) || (t1->data != t2->data))
{
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return false;
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return (this->isIsomorphic(t1->left, t2->left) &&
this->isIsomorphic(t1->right, t2->right)) ||
(this->isIsomorphic(t1->left, t2->right) &&
this->isIsomorphic(t1->right, t2->left));
}
};
int main()
{
BinaryTree *tree1 = new BinaryTree();
BinaryTree *tree2 = new BinaryTree();
BinaryTree *tree3 = new BinaryTree();
BinaryTree *tree4 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
tree1->root = new TreeNode(1);
tree1->root->left = new TreeNode(2);
tree1->root->right = new TreeNode(7);
tree1->root->right->right = new TreeNode(8);
tree1->root->left->right = new TreeNode(3);
tree1->root->left->left = new TreeNode(6);
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
tree2->root = new TreeNode(1);
tree2->root->left = new TreeNode(7);
tree2->root->right = new TreeNode(2);
tree2->root->right->right = new TreeNode(6);
tree2->root->right->left = new TreeNode(3);
tree2->root->left->left = new TreeNode(8);
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
tree3->root = new TreeNode(1);
tree3->root->left = new TreeNode(7);
tree3->root->right = new TreeNode(9);
tree3->root->right->right = new TreeNode(6);
tree3->root->right->left = new TreeNode(3);
tree3->root->left->left = new TreeNode(8);
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
tree4->root = new TreeNode(1);
tree4->root->left = new TreeNode(2);
tree4->root->right = new TreeNode(7);
tree4->root->right->right = new TreeNode(8);
tree4->root->left->right = new TreeNode(3);
tree4->root->left->left = new TreeNode(6);
if (tree1->isIsomorphic(tree1->root, tree2->root))
{
cout << "\n Tree1 and Tree2 is isomorphic";
}
else
{
cout << "\n Tree1 and Tree2 is not isomorphic";
}
if (tree1->isIsomorphic(tree1->root, tree3->root))
{
cout << "\n Tree1 and Tree3 is isomorphic";
}
else
{
cout << "\n Tree1 and Tree3 is not isomorphic";
}
if (tree2->isIsomorphic(tree2->root, tree4->root))
{
cout << "\n Tree2 and Tree4 is isomorphic";
}
else
{
cout << "\n Tree2 and Tree4 is not isomorphic";
}
return 0;
}Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic// Include namespace system
using System;
/*
Csharp program for
Check if two trees are isomorphic
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public Boolean isIsomorphic(TreeNode t1, TreeNode t2)
{
if (t1 == null && t2 == null)
{
// When both t1 and t2 is null
return true;
}
if ((t1 == null || t2 == null) || (t1.data != t2.data))
{
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return false;
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return (this.isIsomorphic(t1.left, t2.left) &&
this.isIsomorphic(t1.right, t2.right)) ||
(this.isIsomorphic(t1.left, t2.right) &&
this.isIsomorphic(t1.right, t2.left));
}
public static void Main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
BinaryTree tree3 = new BinaryTree();
BinaryTree tree4 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(8);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.left = new TreeNode(6);
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(7);
tree2.root.right = new TreeNode(2);
tree2.root.right.right = new TreeNode(6);
tree2.root.right.left = new TreeNode(3);
tree2.root.left.left = new TreeNode(8);
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
tree3.root = new TreeNode(1);
tree3.root.left = new TreeNode(7);
tree3.root.right = new TreeNode(9);
tree3.root.right.right = new TreeNode(6);
tree3.root.right.left = new TreeNode(3);
tree3.root.left.left = new TreeNode(8);
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
tree4.root = new TreeNode(1);
tree4.root.left = new TreeNode(2);
tree4.root.right = new TreeNode(7);
tree4.root.right.right = new TreeNode(8);
tree4.root.left.right = new TreeNode(3);
tree4.root.left.left = new TreeNode(6);
if (tree1.isIsomorphic(tree1.root, tree2.root))
{
Console.Write("\n Tree1 and Tree2 is isomorphic");
}
else
{
Console.Write("\n Tree1 and Tree2 is not isomorphic");
}
if (tree1.isIsomorphic(tree1.root, tree3.root))
{
Console.Write("\n Tree1 and Tree3 is isomorphic");
}
else
{
Console.Write("\n Tree1 and Tree3 is not isomorphic");
}
if (tree2.isIsomorphic(tree2.root, tree4.root))
{
Console.Write("\n Tree2 and Tree4 is isomorphic");
}
else
{
Console.Write("\n Tree2 and Tree4 is not isomorphic");
}
}
}Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphicpackage main
import "fmt"
/*
Go program for
Check if two trees are isomorphic
*/
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node value
me.data = data
me.left = nil
me.right = nil
return me
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial value
me.root = nil
return me
}
func(this BinaryTree) isIsomorphic(t1, t2 *TreeNode) bool {
if t1 == nil && t2 == nil {
// When both t1 and t2 is null
return true
}
if (t1 == nil || t2 == nil) || (t1.data != t2.data) {
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return false
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return (this.isIsomorphic(t1.left, t2.left) && this.isIsomorphic(t1.right, t2.right)) || (this.isIsomorphic(t1.left, t2.right) && this.isIsomorphic(t1.right, t2.left))
}
func main() {
var tree1 * BinaryTree = getBinaryTree()
var tree2 * BinaryTree = getBinaryTree()
var tree3 * BinaryTree = getBinaryTree()
var tree4 * BinaryTree = getBinaryTree()
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
tree1.root = getTreeNode(1)
tree1.root.left = getTreeNode(2)
tree1.root.right = getTreeNode(7)
tree1.root.right.right = getTreeNode(8)
tree1.root.left.right = getTreeNode(3)
tree1.root.left.left = getTreeNode(6)
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
tree2.root = getTreeNode(1)
tree2.root.left = getTreeNode(7)
tree2.root.right = getTreeNode(2)
tree2.root.right.right = getTreeNode(6)
tree2.root.right.left = getTreeNode(3)
tree2.root.left.left = getTreeNode(8)
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
tree3.root = getTreeNode(1)
tree3.root.left = getTreeNode(7)
tree3.root.right = getTreeNode(9)
tree3.root.right.right = getTreeNode(6)
tree3.root.right.left = getTreeNode(3)
tree3.root.left.left = getTreeNode(8)
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
tree4.root = getTreeNode(1)
tree4.root.left = getTreeNode(2)
tree4.root.right = getTreeNode(7)
tree4.root.right.right = getTreeNode(8)
tree4.root.left.right = getTreeNode(3)
tree4.root.left.left = getTreeNode(6)
if tree1.isIsomorphic(tree1.root, tree2.root) {
fmt.Print("\n Tree1 and Tree2 is isomorphic")
} else {
fmt.Print("\n Tree1 and Tree2 is not isomorphic")
}
if tree1.isIsomorphic(tree1.root, tree3.root) {
fmt.Print("\n Tree1 and Tree3 is isomorphic")
} else {
fmt.Print("\n Tree1 and Tree3 is not isomorphic")
}
if tree2.isIsomorphic(tree2.root, tree4.root) {
fmt.Print("\n Tree2 and Tree4 is isomorphic")
} else {
fmt.Print("\n Tree2 and Tree4 is not isomorphic")
}
}Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic<?php
/*
Php program for
Check if two trees are isomorphic
*/
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function isIsomorphic($t1, $t2)
{
if ($t1 == NULL && $t2 == NULL)
{
// When both t1 and t2 is null
return true;
}
if (($t1 == NULL || $t2 == NULL) || ($t1->data != $t2->data))
{
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return false;
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return ($this->isIsomorphic($t1->left, $t2->left) &&
$this->isIsomorphic($t1->right, $t2->right)) ||
($this->isIsomorphic($t1->left, $t2->right) &&
$this->isIsomorphic($t1->right, $t2->left));
}
}
function main()
{
$tree1 = new BinaryTree();
$tree2 = new BinaryTree();
$tree3 = new BinaryTree();
$tree4 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
$tree1->root = new TreeNode(1);
$tree1->root->left = new TreeNode(2);
$tree1->root->right = new TreeNode(7);
$tree1->root->right->right = new TreeNode(8);
$tree1->root->left->right = new TreeNode(3);
$tree1->root->left->left = new TreeNode(6);
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
$tree2->root = new TreeNode(1);
$tree2->root->left = new TreeNode(7);
$tree2->root->right = new TreeNode(2);
$tree2->root->right->right = new TreeNode(6);
$tree2->root->right->left = new TreeNode(3);
$tree2->root->left->left = new TreeNode(8);
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
$tree3->root = new TreeNode(1);
$tree3->root->left = new TreeNode(7);
$tree3->root->right = new TreeNode(9);
$tree3->root->right->right = new TreeNode(6);
$tree3->root->right->left = new TreeNode(3);
$tree3->root->left->left = new TreeNode(8);
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
$tree4->root = new TreeNode(1);
$tree4->root->left = new TreeNode(2);
$tree4->root->right = new TreeNode(7);
$tree4->root->right->right = new TreeNode(8);
$tree4->root->left->right = new TreeNode(3);
$tree4->root->left->left = new TreeNode(6);
if ($tree1->isIsomorphic($tree1->root, $tree2->root))
{
echo("\n Tree1 and Tree2 is isomorphic");
}
else
{
echo("\n Tree1 and Tree2 is not isomorphic");
}
if ($tree1->isIsomorphic($tree1->root, $tree3->root))
{
echo("\n Tree1 and Tree3 is isomorphic");
}
else
{
echo("\n Tree1 and Tree3 is not isomorphic");
}
if ($tree2->isIsomorphic($tree2->root, $tree4->root))
{
echo("\n Tree2 and Tree4 is isomorphic");
}
else
{
echo("\n Tree2 and Tree4 is not isomorphic");
}
}
main();Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic/*
Node JS program for
Check if two trees are isomorphic
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
isIsomorphic(t1, t2)
{
if (t1 == null && t2 == null)
{
// When both t1 and t2 is null
return true;
}
if ((t1 == null || t2 == null) || (t1.data != t2.data))
{
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return false;
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return (this.isIsomorphic(t1.left, t2.left) &&
this.isIsomorphic(t1.right, t2.right)) ||
(this.isIsomorphic(t1.left, t2.right) &&
this.isIsomorphic(t1.right, t2.left));
}
}
function main()
{
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
var tree3 = new BinaryTree();
var tree4 = new BinaryTree();
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(8);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.left = new TreeNode(6);
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(7);
tree2.root.right = new TreeNode(2);
tree2.root.right.right = new TreeNode(6);
tree2.root.right.left = new TreeNode(3);
tree2.root.left.left = new TreeNode(8);
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
tree3.root = new TreeNode(1);
tree3.root.left = new TreeNode(7);
tree3.root.right = new TreeNode(9);
tree3.root.right.right = new TreeNode(6);
tree3.root.right.left = new TreeNode(3);
tree3.root.left.left = new TreeNode(8);
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
tree4.root = new TreeNode(1);
tree4.root.left = new TreeNode(2);
tree4.root.right = new TreeNode(7);
tree4.root.right.right = new TreeNode(8);
tree4.root.left.right = new TreeNode(3);
tree4.root.left.left = new TreeNode(6);
if (tree1.isIsomorphic(tree1.root, tree2.root))
{
process.stdout.write("\n Tree1 and Tree2 is isomorphic");
}
else
{
process.stdout.write("\n Tree1 and Tree2 is not isomorphic");
}
if (tree1.isIsomorphic(tree1.root, tree3.root))
{
process.stdout.write("\n Tree1 and Tree3 is isomorphic");
}
else
{
process.stdout.write("\n Tree1 and Tree3 is not isomorphic");
}
if (tree2.isIsomorphic(tree2.root, tree4.root))
{
process.stdout.write("\n Tree2 and Tree4 is isomorphic");
}
else
{
process.stdout.write("\n Tree2 and Tree4 is not isomorphic");
}
}
main();Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic# Python 3 program for
# Check if two trees are isomorphic
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def isIsomorphic(self, t1, t2) :
if (t1 == None and t2 == None) :
# When both t1 and t2 is null
return True
if ((t1 == None or t2 == None) or(t1.data != t2.data)) :
# When one tree t1 or t2 node is empty or
# t1 and t2 node value not similar
return False
# When t1 and t2 tree are similar
# Or t1 and t2 child are flipped to each other
return (self.isIsomorphic(t1.left, t2.left) and
self.isIsomorphic(t1.right, t2.right)) or (self.isIsomorphic(t1.left, t2.right) and
self.isIsomorphic(t1.right, t2.left))
def main() :
tree1 = BinaryTree()
tree2 = BinaryTree()
tree3 = BinaryTree()
tree4 = BinaryTree()
# 1
# / \
# 2 7
# / \ \
# 6 3 8
# ------------
# Binary tree A
tree1.root = TreeNode(1)
tree1.root.left = TreeNode(2)
tree1.root.right = TreeNode(7)
tree1.root.right.right = TreeNode(8)
tree1.root.left.right = TreeNode(3)
tree1.root.left.left = TreeNode(6)
# 1
# / \
# 7 2
# / / \
# 8 3 6
# ------------
# Binary tree B
tree2.root = TreeNode(1)
tree2.root.left = TreeNode(7)
tree2.root.right = TreeNode(2)
tree2.root.right.right = TreeNode(6)
tree2.root.right.left = TreeNode(3)
tree2.root.left.left = TreeNode(8)
# 1
# / \
# 7 9
# / / \
# 8 3 6
# ------------
# Binary tree C
tree3.root = TreeNode(1)
tree3.root.left = TreeNode(7)
tree3.root.right = TreeNode(9)
tree3.root.right.right = TreeNode(6)
tree3.root.right.left = TreeNode(3)
tree3.root.left.left = TreeNode(8)
# 1
# / \
# 2 7
# / \ \
# 6 3 8
# ------------
# Binary tree D
tree4.root = TreeNode(1)
tree4.root.left = TreeNode(2)
tree4.root.right = TreeNode(7)
tree4.root.right.right = TreeNode(8)
tree4.root.left.right = TreeNode(3)
tree4.root.left.left = TreeNode(6)
if (tree1.isIsomorphic(tree1.root, tree2.root)) :
print("\n Tree1 and Tree2 is isomorphic", end = "")
else :
print("\n Tree1 and Tree2 is not isomorphic", end = "")
if (tree1.isIsomorphic(tree1.root, tree3.root)) :
print("\n Tree1 and Tree3 is isomorphic", end = "")
else :
print("\n Tree1 and Tree3 is not isomorphic", end = "")
if (tree2.isIsomorphic(tree2.root, tree4.root)) :
print("\n Tree2 and Tree4 is isomorphic", end = "")
else :
print("\n Tree2 and Tree4 is not isomorphic", end = "")
if __name__ == "__main__": main()Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic# Ruby program for
# Check if two trees are isomorphic
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def isIsomorphic(t1, t2)
if (t1 == nil && t2 == nil)
# When both t1 and t2 is null
return true
end
if ((t1 == nil || t2 == nil) || (t1.data != t2.data))
# When one tree t1 or t2 node is empty or
# t1 and t2 node value not similar
return false
end
# When t1 and t2 tree are similar
# Or t1 and t2 child are flipped to each other
return (self.isIsomorphic(t1.left, t2.left) &&
self.isIsomorphic(t1.right, t2.right)) ||
(self.isIsomorphic(t1.left, t2.right) &&
self.isIsomorphic(t1.right, t2.left))
end
end
def main()
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
tree3 = BinaryTree.new()
tree4 = BinaryTree.new()
# 1
# / \
# 2 7
# / \ \
# 6 3 8
# ------------
# Binary tree A
tree1.root = TreeNode.new(1)
tree1.root.left = TreeNode.new(2)
tree1.root.right = TreeNode.new(7)
tree1.root.right.right = TreeNode.new(8)
tree1.root.left.right = TreeNode.new(3)
tree1.root.left.left = TreeNode.new(6)
# 1
# / \
# 7 2
# / / \
# 8 3 6
# ------------
# Binary tree B
tree2.root = TreeNode.new(1)
tree2.root.left = TreeNode.new(7)
tree2.root.right = TreeNode.new(2)
tree2.root.right.right = TreeNode.new(6)
tree2.root.right.left = TreeNode.new(3)
tree2.root.left.left = TreeNode.new(8)
# 1
# / \
# 7 9
# / / \
# 8 3 6
# ------------
# Binary tree C
tree3.root = TreeNode.new(1)
tree3.root.left = TreeNode.new(7)
tree3.root.right = TreeNode.new(9)
tree3.root.right.right = TreeNode.new(6)
tree3.root.right.left = TreeNode.new(3)
tree3.root.left.left = TreeNode.new(8)
# 1
# / \
# 2 7
# / \ \
# 6 3 8
# ------------
# Binary tree D
tree4.root = TreeNode.new(1)
tree4.root.left = TreeNode.new(2)
tree4.root.right = TreeNode.new(7)
tree4.root.right.right = TreeNode.new(8)
tree4.root.left.right = TreeNode.new(3)
tree4.root.left.left = TreeNode.new(6)
if (tree1.isIsomorphic(tree1.root, tree2.root))
print("\n Tree1 and Tree2 is isomorphic")
else
print("\n Tree1 and Tree2 is not isomorphic")
end
if (tree1.isIsomorphic(tree1.root, tree3.root))
print("\n Tree1 and Tree3 is isomorphic")
else
print("\n Tree1 and Tree3 is not isomorphic")
end
if (tree2.isIsomorphic(tree2.root, tree4.root))
print("\n Tree2 and Tree4 is isomorphic")
else
print("\n Tree2 and Tree4 is not isomorphic")
end
end
main()Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic/*
Scala program for
Check if two trees are isomorphic
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data, null, null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def isIsomorphic(t1: TreeNode, t2: TreeNode): Boolean = {
if (t1 == null && t2 == null)
{
// When both t1 and t2 is null
return true;
}
if ((t1 == null || t2 == null) || (t1.data != t2.data))
{
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return false;
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return (isIsomorphic(t1.left, t2.left) &&
isIsomorphic(t1.right, t2.right)) ||
(isIsomorphic(t1.left, t2.right) &&
isIsomorphic(t1.right, t2.left));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: BinaryTree = new BinaryTree();
var tree2: BinaryTree = new BinaryTree();
var tree3: BinaryTree = new BinaryTree();
var tree4: BinaryTree = new BinaryTree();
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
tree1.root = new TreeNode(1);
tree1.root.left = new TreeNode(2);
tree1.root.right = new TreeNode(7);
tree1.root.right.right = new TreeNode(8);
tree1.root.left.right = new TreeNode(3);
tree1.root.left.left = new TreeNode(6);
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
tree2.root = new TreeNode(1);
tree2.root.left = new TreeNode(7);
tree2.root.right = new TreeNode(2);
tree2.root.right.right = new TreeNode(6);
tree2.root.right.left = new TreeNode(3);
tree2.root.left.left = new TreeNode(8);
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
tree3.root = new TreeNode(1);
tree3.root.left = new TreeNode(7);
tree3.root.right = new TreeNode(9);
tree3.root.right.right = new TreeNode(6);
tree3.root.right.left = new TreeNode(3);
tree3.root.left.left = new TreeNode(8);
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
tree4.root = new TreeNode(1);
tree4.root.left = new TreeNode(2);
tree4.root.right = new TreeNode(7);
tree4.root.right.right = new TreeNode(8);
tree4.root.left.right = new TreeNode(3);
tree4.root.left.left = new TreeNode(6);
if (tree1.isIsomorphic(tree1.root, tree2.root))
{
print("\n Tree1 and Tree2 is isomorphic");
}
else
{
print("\n Tree1 and Tree2 is not isomorphic");
}
if (tree1.isIsomorphic(tree1.root, tree3.root))
{
print("\n Tree1 and Tree3 is isomorphic");
}
else
{
print("\n Tree1 and Tree3 is not isomorphic");
}
if (tree2.isIsomorphic(tree2.root, tree4.root))
{
print("\n Tree2 and Tree4 is isomorphic");
}
else
{
print("\n Tree2 and Tree4 is not isomorphic");
}
}
}Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic/*
Swift 4 program for
Check if two trees are isomorphic
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func isIsomorphic(_ t1: TreeNode? , _ t2 : TreeNode? ) -> Bool
{
if (t1 == nil && t2 == nil)
{
// When both t1 and t2 is null
return true;
}
if ((t1 == nil || t2 == nil) || (t1!.data != t2!.data))
{
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return false;
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return (self.isIsomorphic(t1!.left, t2!.left) &&
self.isIsomorphic(t1!.right, t2!.right)) ||
(self.isIsomorphic(t1!.left, t2!.right) &&
self.isIsomorphic(t1!.right, t2!.left));
}
}
func main()
{
let tree1: BinaryTree = BinaryTree();
let tree2: BinaryTree = BinaryTree();
let tree3: BinaryTree = BinaryTree();
let tree4: BinaryTree = BinaryTree();
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
tree1.root = TreeNode(1);
tree1.root!.left = TreeNode(2);
tree1.root!.right = TreeNode(7);
tree1.root!.right!.right = TreeNode(8);
tree1.root!.left!.right = TreeNode(3);
tree1.root!.left!.left = TreeNode(6);
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
tree2.root = TreeNode(1);
tree2.root!.left = TreeNode(7);
tree2.root!.right = TreeNode(2);
tree2.root!.right!.right = TreeNode(6);
tree2.root!.right!.left = TreeNode(3);
tree2.root!.left!.left = TreeNode(8);
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
tree3.root = TreeNode(1);
tree3.root!.left = TreeNode(7);
tree3.root!.right = TreeNode(9);
tree3.root!.right!.right = TreeNode(6);
tree3.root!.right!.left = TreeNode(3);
tree3.root!.left!.left = TreeNode(8);
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
tree4.root = TreeNode(1);
tree4.root!.left = TreeNode(2);
tree4.root!.right = TreeNode(7);
tree4.root!.right!.right = TreeNode(8);
tree4.root!.left!.right = TreeNode(3);
tree4.root!.left!.left = TreeNode(6);
if (tree1.isIsomorphic(tree1.root, tree2.root))
{
print("\n Tree1 and Tree2 is isomorphic", terminator: "");
}
else
{
print("\n Tree1 and Tree2 is not isomorphic", terminator: "");
}
if (tree1.isIsomorphic(tree1.root, tree3.root))
{
print("\n Tree1 and Tree3 is isomorphic", terminator: "");
}
else
{
print("\n Tree1 and Tree3 is not isomorphic", terminator: "");
}
if (tree2.isIsomorphic(tree2.root, tree4.root))
{
print("\n Tree2 and Tree4 is isomorphic", terminator: "");
}
else
{
print("\n Tree2 and Tree4 is not isomorphic", terminator: "");
}
}
main();Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic/*
Kotlin program for
Check if two trees are isomorphic
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun isIsomorphic(t1: TreeNode ? , t2 : TreeNode ? ): Boolean
{
if (t1 == null && t2 == null)
{
// When both t1 and t2 is null
return true;
}
if ((t1 == null || t2 == null) || (t1.data != t2.data))
{
// When one tree t1 or t2 node is empty or
// t1 and t2 node value not similar
return false;
}
// When t1 and t2 tree are similar
// Or t1 and t2 child are flipped to each other
return (this.isIsomorphic(t1.left, t2.left) &&
this.isIsomorphic(t1.right, t2.right)) ||
(this.isIsomorphic(t1.left, t2.right) &&
this.isIsomorphic(t1.right, t2.left));
}
}
fun main(args: Array < String > ): Unit
{
val tree1: BinaryTree = BinaryTree();
val tree2: BinaryTree = BinaryTree();
val tree3: BinaryTree = BinaryTree();
val tree4: BinaryTree = BinaryTree();
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree A
*/
tree1.root = TreeNode(1);
tree1.root?.left = TreeNode(2);
tree1.root?.right = TreeNode(7);
tree1.root?.right?.right = TreeNode(8);
tree1.root?.left?.right = TreeNode(3);
tree1.root?.left?.left = TreeNode(6);
/*
1
/ \
7 2
/ / \
8 3 6
------------
Binary tree B
*/
tree2.root = TreeNode(1);
tree2.root?.left = TreeNode(7);
tree2.root?.right = TreeNode(2);
tree2.root?.right?.right = TreeNode(6);
tree2.root?.right?.left = TreeNode(3);
tree2.root?.left?.left = TreeNode(8);
/*
1
/ \
7 9
/ / \
8 3 6
------------
Binary tree C
*/
tree3.root = TreeNode(1);
tree3.root?.left = TreeNode(7);
tree3.root?.right = TreeNode(9);
tree3.root?.right?.right = TreeNode(6);
tree3.root?.right?.left = TreeNode(3);
tree3.root?.left?.left = TreeNode(8);
/*
1
/ \
2 7
/ \ \
6 3 8
------------
Binary tree D
*/
tree4.root = TreeNode(1);
tree4.root?.left = TreeNode(2);
tree4.root?.right = TreeNode(7);
tree4.root?.right?.right = TreeNode(8);
tree4.root?.left?.right = TreeNode(3);
tree4.root?.left?.left = TreeNode(6);
if (tree1.isIsomorphic(tree1.root, tree2.root))
{
print("\n Tree1 and Tree2 is isomorphic");
}
else
{
print("\n Tree1 and Tree2 is not isomorphic");
}
if (tree1.isIsomorphic(tree1.root, tree3.root))
{
print("\n Tree1 and Tree3 is isomorphic");
}
else
{
print("\n Tree1 and Tree3 is not isomorphic");
}
if (tree2.isIsomorphic(tree2.root, tree4.root))
{
print("\n Tree2 and Tree4 is isomorphic");
}
else
{
print("\n Tree2 and Tree4 is not isomorphic");
}
}Output
Tree1 and Tree2 is isomorphic
Tree1 and Tree3 is not isomorphic
Tree2 and Tree4 is isomorphic
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment