Tree Isomorphism Problem in C++

Hello everyone, in this tutorial we will discuss the tree isomorphism problem in C++. Two trees are said to be isomorphic if one of the trees can be obtained by flipping left and right children of some of the nodes of other tree. The flipping is done in such a way that when a left child is swapped with the right child, all the lower-level nodes are also flipped as well without any change in the order i.e. the whole subtree is swapped. Consider the given two trees.

tree 1                   1                         
                        / \
                       2   3
                     /  \ /  \
                    4   5 6   7
                   /
                  8 



 tree 2                  1
                        / \
                       3   2
                     /  \ /  \
                    6   7 5   4 
                               \
                                8

In the above example, we can easily get the second tree by swapping children of node 1, node 2 and node 4 from the first tree. Hence tree1 and tree2 are isomorphic.

C++ Tree Isomorphism Problem

Here, we will write a C++ program to detect whether two given trees are isomorphic or not. The algorithm for this problem is as follows:

Algorithm

Two trees, tree1 and tree2 are isomorphic if one of the following condition is satisfied:

  • Both trees are empty. Two NULL trees are always isomorphic.
  • Root of tree1 and root of tree2 has same data and left child of tree1 is isomorphic to left child of tree2 and right child of tree1 is isomorphic to right child of tree2.
  • Root of tree1 and root of tree2 has same data and left child of tree1 is isomorphic to right child of tree2 and right child of tree1 is isomorphic to left child of tree2.

Implementation of above algorithm in C++

#include <iostream>
#include <bits/stdc++.h>

class treenode{
    public:
    int data;
    treenode *left, *right;
    
};

bool isomorphic_tree(treenode *tree1, treenode *tree2)
{
    if(!tree1 && !tree2)
        return true;
        
    if(!tree1 || !tree2)
        return false;
    
    if(tree1->data != tree2->data)
        return false;
        
    if((isomorphic_tree(tree1->left, tree2->left) && isomorphic_tree(tree1->right, tree2->right)) || 
(isomorphic_tree(tree1->left, tree2->right) && isomorphic_tree(tree1->right, tree2->left)))
        return true;
        
}

treenode* create_node(int data)
{
    treenode *node = new treenode();
    node->data = data;
    node->left = node->right = NULL;
    
    return node;
}

int main()
{
    treenode *tree1 = create_node(1);
    tree1->left = create_node(2); 
    tree1->right = create_node(3); 
    tree1->left->left = create_node(4); 
    tree1->left->right = create_node(5); 
    tree1->right->left = create_node(6);
    tree1->right->right = create_node(7);
    tree1->left->left->left = create_node(8); 
  
    treenode *tree2 = create_node(1); 
    tree2->left = create_node(3); 
    tree2->right = create_node(2); 
    tree2->left->left = create_node(6); 
    tree2->left->right = create_node(7); 
    tree2->right->left = create_node(5);
    tree2->right->right = create_node(4);
    tree2->right->right->right = create_node(8);
        
    if(isomorphic_tree(tree1, tree2))
        std::cout << "Trees are isomorphic.\n";
        
    else
        std::cout << "Trees are not isomorphic.\n";
    
    return 0;
}

Output:

Trees are isomorphic.

Also read: Stock Span Problem in C++

Leave a Reply

Your email address will not be published. Required fields are marked *