C++ program to check if two trees are identical using recursion
Description:
This Program is to check if two trees are identical using recursion.
For Example:
Input :
The Elements of tree1 : 1 , 2, 3, 4, 5
The Elements of tree2 : 1 , 2, 3, 4, 5
Output :
Both tree are identical.
Program :
//C++ program to check if two trees are identical using recursion
using namespace std;
// tree node
struct Node
{
int data;
Node *left, *right;
};
// returns a new tree Node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
//return true if they are identical
bool Trees(struct Node* root1, struct Node* root2)
{
// if both empty
if (root1==NULL && root2==NULL)
return true;
// if both are non empty then comparing them
if (root1!=NULL && root2!=NULL)
{
return
(
root1->data == root2->data &&
Trees(root1->left, root2->left) &&
Trees(root1->right, root2->right)
);
}
//if one empty, one not -> false
return false;
}
int main()
{
struct Node *root1 = newNode(1);
struct Node *root2 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root2->left = newNode(2);
root2->right = newNode(3);
root2->left->left = newNode(4);
root2->left->right = newNode(5);
if(Trees(root1, root2))
cout<<"Both tree are identical.";
else
cout<<"Trees are not identical.";
getchar();
return 0;
}
Comments