- 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.

- If both root1 and root2 are NULL, then return true.
- If only one is NULL and other is Not NULL, then return false.
- Check data of both nodes are same or not(root1->data == root->data).
- Recursively, check left sub tree of both root1 and root2 is identical or not(isIdentical(root1->left, root2->left)).
- Recursively, check right sub tree of both root1 and root2 is identical or not(isIdentical(root1->right, root2->right).
- 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.