To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees.
Algorithm:
sameTree(tree1, tree2)
1： If both trees are empty then return 1.
2： Else If both trees are non -empty
(a) Check data of the root nodes (tree1->data == tree2->data)
(b) Check left subtrees recursively i.e., call sameTree(
tree1->left_subtree, tree2->left_subtree)
(c) Check right subtrees recursively i.e., call sameTree(
tree1->right_subtree, tree2->right_subtree)
(d) If a,b and c are true then return 1.
3： Else return 0 (one is empty and other is not)
/* Given two trees, return true if they are
structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
/*1. both empty */
if (a==NULL && b==NULL)
return 1;
/* 2. both non-empty -> compare them */
if (a!=NULL && b!=NULL)
{
return
(
a->data == b->data &&
identicalTrees(a->left, b->left) &&
identicalTrees(a->right, b->right)
);
}
/* 3. one empty, one not -> false */
return 0;
}
