C Program to check whether two trees are identical or not

Two trees are identical if they have the same data arrangement w.r.t each other.

Algorithm:

identicalTrees(Tree1,Tree2)

1. Check if both trees are empty if so then return 1;

2. Recursively check for the following tree:

         a.       Return 1 if both have same data

         b.      Check left tree recursively : identicalTrees(tree1->left,tree2->left)

         c.       Check right tree recursively : identicalTrees(tree1->right,tree2->right)

         d.      Return 1 if a,b,c are true else return 0;

      3. Return 0 if one tree is empty and other is not.

    

   Program:

   

   /*Program to check whether two trees are identical or not*/

   #include<stdio.h> /*for printf & scanf*/

   #include<stdlib.h>/*fro malloc & calloc */

   /*structure to define tree node*/

   struct node

  {

    int data;

    struct node* left;

    struct node* right;

   };

   /*function to insert a new node in tree*/

   struct node* insert(int new_data)

  {

    struct node* temp=(struct node*) malloc(sizeof(struct node));

    temp->data=new_data;

    temp->left=NULL;

    temp->right=NULL;

    return (temp);

  };

   /*function return true or 1 if both trees are idential*/

   int identicalTrees(struct node* tree1,struct node* tree2)

   

{
    else if(tree1!=NULL && tree2!=NULL)
}
}
    tree1=insert(1);
    tree2=insert(1);
        if(identicalTrees(tree1,tree2))
    return 0;

    if(tree1==NULL && tree2==NULL)

       return 1;

        return(

               (tree1->data==tree2->data)&&

               (identicalTrees(tree1->left,tree2->left))&&

               (identicalTrees(tree1->right,tree2->right))

               );

    else

        return 0;

   int main()

  {

    struct node*tree1=NULL;

    struct node*tree2=NULL;

    tree1->left=insert(2);

    tree1->right=insert(3);

    tree1->left->left=insert(4);

    tree1->left->right=insert(5);

    tree2->left=insert(2);

    tree2->right=insert(3);

    tree2->left->left=insert(4);

    tree2->left->right=insert(5);

            printf("Both tree are identical");

        else

            printf("Both tree are not identical");

   

   }

Viva La Raza

Sid