Program to Check if Two Trees are Identical

  • Write a program in C to check if Two Trees are same.
  • How to compare two binary trees for equality.

Two binary trees are identical, if both trees have same set of nodes arranges in same order. To check whether two binary trees are identical or not we will use recursion and divide a problem in to identical sub-problems. We will traverse both trees simultaneously and recursively compare left and right sub trees of both trees for equality.

Algorithm to determine if two trees are identical
Let "root1" and "root2" be the root pointer of two binary tree.
  1. If both root1 and root2 are NULL, then return true.
  2. If only one is NULL and other is Not NULL, then return false.
  3. Check data of both nodes are same or not(root1->data == root->data).
  4. Recursively, check left sub tree of both root1 and root2 is identical or not(isIdentical(root1->left, root2->left)).
  5. Recursively, check right sub tree of both root1 and root2 is identical or not(isIdentical(root1->right, root2->right).
  6. If all three above checks are true then both binary trees are identical otherwise not identical.

In this program, we will use a recursive function "isIdentical" which check whether two binary trees are identical as per algorithm mentioned above. 

int isIdentical(struct node *first, struct node *second){
    /*If both are NULL , then Identical */
    if(first == NULL && second == NULL)
        return TRUE;
    /* If only one tree is NULL, then not Identical */
    if(first == NULL || second == NULL)
        return FALSE;
    
    /* IF left sub-trees, right subtrees and root node of 
    both trees are same then both trees are identical */
    if(isIdentical(first->left, second->left) && 
       isIdentical(first->right, second->right) && 
       first->data == second->data){
           return TRUE;
    } else {
        return FALSE;
    }
}

C program to check if two binary trees are same

#include <stdio.h>

#define TRUE 1
#define FALSE 0

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns following tree
            1
           / \
         2    3
        / \  / \
       4  5 6  7
      /
     8
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
    // Level 2 nodes 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
    // Level 3 nodes
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->left = getNewNode(6);
    root->right->right = getNewNode(7);
    // Level 4 nodes
    root->left->left->left = getNewNode(8);
    
    return root;

}

/*
 Checks, if two trees are same or not  
*/
int isIdentical(struct node *first, struct node *second){
    /*If both are NULL , then Identical */
    if(first == NULL && second == NULL)
        return TRUE;
    /* If only one tree is NULL, then not Identical */
    if(first == NULL || second == NULL)
        return FALSE;
    
    /* IF left sub-trees, right subtrees and root node of 
    both trees are same then both trees are identical */
    if(isIdentical(first->left, second->left) && 
       isIdentical(first->right, second->right) && 
       first->data == second->data){
           return TRUE;
    } else {
        return FALSE;
    }
}

int main() {
    /*Creating two identical trees */
    struct node *root1 = generateBTree();    
    struct node *root2 = generateBTree();
    
    if(isIdentical(root1, root2)){
        printf("Both trees are identical.\n");
    } else {
        printf("Both trees are not identical.\n");
    }
    
    /* Now changing one node of second tree */
    root2->left->data = 10;
    if(isIdentical(root1, root2)){
        printf("Both trees are identical.\n");
    } else {
        printf("Both trees are not identical.\n");
    }
    
    getchar();
    return 0; 
}
Output
Both trees are identical.
Both trees are not identical.
Posted by
Labels: