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

isomorphic tree is depend node values and depend on tree structure. Let see an example of non isomorphic trees.

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 isomorphic
package 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







© 2021, kalkicode.com, All rights reserved