Trees are identical or not

Implement a code to determine whether given trees are identical or not.

Time complexity : O(m)

Number of nodes in tree1 = m
Number of nodes in tree2 = n, m < n.
Then Time Complexity = O(m).

Example

In the given image

 

Algorithm

Step 1 : We take two trees as input.
Step 2 : If given two trees are empty then they are identical.
a)    Tree1 = NULL and Tree2 = NULL, print true.
Step 3 : If both trees are not empty, then first compare root nodes, then recursively go to the left subtree and apply the same function on it. Then go to the right subtree and apply function there.
a)    Check root nodes are equal or not.
b)    Then go to left subtree call identical(left subtree).
c)    Then go to right subtree call identical(right subtree).
d)    If these three are true then, print True.
Step 4 : Else print false.
Step 5 :  call the function on the given two trees, if true print “Identical”, else print “Not Identical”.

C++ Program

/* Code for to check whether two trees are identical or not*/
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

/* implementation of the binary tree with pointers to left child node and right child node*/
struct node
{
     char data;
     struct node* left;
     struct node* right;
};
/*In this function we are creating a node with the given data and null left and right pointers  */ 
struct node* CreateNewNode(char data)
{
     struct node* node = (struct node*)malloc(sizeof(struct node));
     node->data = data;
     node->left = NULL;
     node->right = NULL;
     return(node);
}
/*function to check whether trees are identical or not*/
bool CheckIdentical(struct node* rootTree1, struct node* tree2)
{
    if (rootTree1==NULL && tree2==NULL)
    {        
        return true;
    }
    if (rootTree1!=NULL && tree2!=NULL)
    {
        bool identical = rootTree1->data == tree2->data &&CheckIdentical(rootTree1->left, tree2->left)&&CheckIdentical(rootTree1->right, tree2->right);
        return identical;
    }
    return false;
} 

/*main code*/
int main()
{
    /*Here we are creating rootTree1*/
     struct node *rootTree1  = CreateNewNode('A');
     rootTree1->left             = CreateNewNode('B');
     rootTree1->right           = CreateNewNode('C');
     rootTree1->right->left     = CreateNewNode('H');
     rootTree1->right->right      = CreateNewNode('I');
     rootTree1->left->left     = CreateNewNode('D');
     rootTree1->left->left->left     = CreateNewNode('F');
     rootTree1->left->left->right     = CreateNewNode('G');
     rootTree1->left->right   = CreateNewNode('E'); 
     /*Here we are creating tree2*/
     struct node *rootTree2  = CreateNewNode('A');
     rootTree2->left             = CreateNewNode('B');
     rootTree2->right           = CreateNewNode('C');
     rootTree2->right->left     = CreateNewNode('H');
     rootTree2->right->right      = CreateNewNode('I');
     rootTree2->left->left     = CreateNewNode('D');
     rootTree2->left->left->right     = CreateNewNode('F');
     rootTree2->left->left->left     = CreateNewNode('G');
     rootTree2->left->right   = CreateNewNode('E'); 
    /*checking trees are identical or not*/
    if(CheckIdentical(rootTree1, rootTree2))
    {
        cout<<("Trees are identical");
    }
    else
    {
       cout<<("Trees are Not identical");
    }
  return 0;
}
Try It


Next > < Prev
Scroll to Top