Determine if two binary trees are identical or not

by · January 26, 2021

“Determine if two binary trees are identical or not” is a basic problem of tree data structure. Here, we are given two binary trees and our task is to write a program to determine if given two binary trees are identical or not.

Determine if two binary trees are identical or not

We can solve this problem both recursively and iteratively. The basic idea in both the solution is to check whether root node of first tree is equal to root node of second tree. If value of root node of both trees is equal then, we recursively or iteratively traverse the left subtree and right subtree and check whether left subtree of first tree is equal to left subtree of second tree and right subtree of first tree is equal to right subtree of second tree.

If at any point of traversal and comparison, the left and right subtree of first tree is not equal to left and right subtree of second tree, then we return false.

Method 1: Recursive Solution

C++ Program to Determine if two binary trees are identical or not is as follows:

/* C++ Program to determine if two binary trees are identical or not */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to determine if two binary trees are identical or not */
bool checkidentical(Node *root1, Node *root2)
{
    /* Basic Case: Both Trees are empty */
    if(root1 == NULL && root2 == NULL)
    {
        return true;
    }
    
    /* If one tree is empty and other not */
    if(root1 == NULL || root2 == NULL)
    {
        return false;
    }
    
    /*
        If data of nodes are equal, then recursively check left
        subtree and right subtree of both given binary trees
    */
    if(root1 -> data == root2 -> data)
    {
        return checkidentical(root1 -> left, root2 -> left) &&
        checkidentical(root1 -> right, root2 -> right);
    }
    else
    {
        return false;
    }
}

int main()
{
    /* Creating a Binary trees and inserting some nodes in it */
    Node *root1 = NULL;
    Node *root2 = NULL;
    
    root1 = new Node(1);
    root1 -> left = new Node(2);
    root1 -> right = new Node(3);
    root1 -> left -> left = new Node(4);
    root1 -> left -> right = new Node(5);
    root1 -> right -> left = new Node(6);
    root1 -> right -> right = new Node (7);
    root1 -> left -> right -> left = new Node(8);
    root1 -> right -> left -> right = new Node(9);
    
    root2 = new Node(1);
    root2 -> left = new Node(2);
    root2 -> right = new Node(3);
    root2 -> left -> left = new Node(4);
    root2 -> left -> right = new Node(5);
    root2 -> right -> left = new Node(6);
    root2 -> right -> right = new Node (7);
    root2 -> left -> right -> left = new Node(8);
    root2 -> right -> left -> right = new Node(9);
    
    
    /* Calling function to determine if two binary trees are identical or not */
    if(checkidentical(root1, root2) == true)
    {
        cout<<"Given Binary Trees are Identical!!";
    }
    else
    {
        cout<<"Given Binary Tree are not Identical!!";
    }
}

OUTPUT:

Given Binary Trees are Identical!!

Method 2: Iterative Solution

C++ Program to Determine if two binary trees are identical or not is as follows:

/* C++ Program to determine if two binary trees are identical or not */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to determine if two binary trees are identical or not */
bool checkidentical(Node *root1, Node *root2)
{
     /* Basic Case: Both Trees are empty */
    if(root1 == NULL && root2 == NULL)
    {
        return true;
    }
    
    /* If one tree is empty and other not */
    if(root1 == NULL || root2 == NULL)
    {
        return false;
    }
    
    /* Initialize queue and push root into it */
    queue<Node *> que1;
    queue<Node *> que2;
    
    que1.push(root1);
    que2.push(root2);
    
    while(!que1.empty() && !que2.empty())
    {
        Node *temp1 = que1.front();
        Node *temp2 = que2.front();
        
        /* 
            If data of both nodes are same, 
            then traverse trees further
        */
        if(temp1 -> data == temp2 -> data)
        {
            que1.pop();
            que2.pop();
            
            /*
                If left child of both tree exists, push it into queue
            */
            if(temp1 -> left && temp2 -> left)
            {
                que1.push(temp1 -> left);
                que2.push(temp2 -> left);
            }
            /*
                If left child of only one tree exists, then return false.
            */
            else if(temp1 -> left || temp2 -> left)
            {
                return false;
            }
            
            /*
                If right child of both tree exists, push it into queue
            */
            if(temp1 -> right && temp2 -> right)
            {
                que1.push(temp1 -> right);
                que2.push(temp2 -> right);
            }
            /*
                If right child of only one tree exists, then return false.
            */
            else if(temp1 -> right || temp2 -> right)
            {
                return false;
            }
        }
        /*
            If data of both nodes are not same, 
            then return false
        */
        else
        {
            return false;
        }
    }
    return true;
}

int main()
{
    /* Creating a Binary trees and inserting some nodes in it */
    Node *root1 = NULL;
    Node *root2 = NULL;
    
    root1 = new Node(1);
    root1 -> left = new Node(2);
    root1 -> right = new Node(3);
    root1 -> left -> left = new Node(4);
    root1 -> left -> right = new Node(5);
    root1 -> right -> left = new Node(6);
    root1 -> right -> right = new Node (7);
    root1 -> left -> right -> left = new Node(8);
    root1 -> right -> left -> right = new Node(9);
    
    root2 = new Node(1);
    root2 -> left = new Node(2);
    root2 -> right = new Node(3);
    root2 -> left -> left = new Node(4);
    root2 -> left -> right = new Node(5);
    root2 -> right -> left = new Node(6);
    root2 -> right -> right = new Node (7);
    root2 -> left -> right -> left = new Node(8);
    root2 -> right -> left -> right = new Node(9);
    
    
    /* Calling function to determine if two binary trees are identical or not */
    if(checkidentical(root1, root2) == true)
    {
        cout<<"Given Binary Trees are Identical!!";
    }
    else
    {
        cout<<"Given Binary Tree are not Identical!!";
    }
}

OUTPUT:

Given Binary Trees are Identical!!

Related Posts:

  1. Binary Tree Traversals
  2. Print All Leaf Nodes of a Binary Tree
  3. Count Number of Nodes in a Binary Tree
  4. Print Alternate Levels of Binary Tree
  5. Maximum Width of Binary Tree
  6. Level Order Tree Traversal
  7. Left View of Binary Tree
  8. Right View of Binary Tree
  9. Compute Height of Binary Tree
  10. Inorder Tree Traversal Using Stack
  11. Preorder Tree Trasversal Using Stack
  12. Postorder Tree Traversal Using Stack
  13. Vertical Order Tree Traversal
  14. Top View of Binary Tree
  15. Bottom View of Binary Tree
  16. Delete Complete Binary Tree
  17. Check if two trees are mirror Trees of Each Other
  18. Convert Binary Tree to its Mirror Tree
  19. Check if Binary Tree is Symmetric or Not
  20. Print All Root to Leaf Paths in a Binary Tree

You may also like...