# Determine if two binary trees are identical or not

“Determine if two binary trees are identical or not” is a basic problem of tree data structure. Here, we are given two binary trees and our task is to write a program to determine if given two binary trees are identical or not.

We can solve this problem both recursively and iteratively. The basic idea in both the solution is to check whether root node of first tree is equal to root node of second tree. If value of root node of both trees is equal then, we recursively or iteratively traverse the left subtree and right subtree and check whether left subtree of first tree is equal to left subtree of second tree and right subtree of first tree is equal to right subtree of second tree.

If at any point of traversal and comparison, the left and right subtree of first tree is not equal to left and right subtree of second tree, then we return false.

Method 1: Recursive Solution

#### C++ Program to Determine if two binary trees are identical or not is as follows:

```/* C++ Program to determine if two binary trees are identical or not */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;

/* Function to determine if two binary trees are identical or not */
bool checkidentical(Node *root1, Node *root2)
{
/* Basic Case: Both Trees are empty */
if(root1 == NULL && root2 == NULL)
{
return true;
}

/* If one tree is empty and other not */
if(root1 == NULL || root2 == NULL)
{
return false;
}

/*
If data of nodes are equal, then recursively check left
subtree and right subtree of both given binary trees
*/
if(root1 -> data == root2 -> data)
{
return checkidentical(root1 -> left, root2 -> left) &&
checkidentical(root1 -> right, root2 -> right);
}
else
{
return false;
}
}

int main()
{
/* Creating a Binary trees and inserting some nodes in it */
Node *root1 = NULL;
Node *root2 = NULL;

root1 = new Node(1);
root1 -> left = new Node(2);
root1 -> right = new Node(3);
root1 -> left -> left = new Node(4);
root1 -> left -> right = new Node(5);
root1 -> right -> left = new Node(6);
root1 -> right -> right = new Node (7);
root1 -> left -> right -> left = new Node(8);
root1 -> right -> left -> right = new Node(9);

root2 = new Node(1);
root2 -> left = new Node(2);
root2 -> right = new Node(3);
root2 -> left -> left = new Node(4);
root2 -> left -> right = new Node(5);
root2 -> right -> left = new Node(6);
root2 -> right -> right = new Node (7);
root2 -> left -> right -> left = new Node(8);
root2 -> right -> left -> right = new Node(9);

/* Calling function to determine if two binary trees are identical or not */
if(checkidentical(root1, root2) == true)
{
cout<<"Given Binary Trees are Identical!!";
}
else
{
cout<<"Given Binary Tree are not Identical!!";
}
}
```

OUTPUT:

`Given Binary Trees are Identical!!`

Method 2: Iterative Solution

#### C++ Program to Determine if two binary trees are identical or not is as follows:

```/* C++ Program to determine if two binary trees are identical or not */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;

/* Function to determine if two binary trees are identical or not */
bool checkidentical(Node *root1, Node *root2)
{
/* Basic Case: Both Trees are empty */
if(root1 == NULL && root2 == NULL)
{
return true;
}

/* If one tree is empty and other not */
if(root1 == NULL || root2 == NULL)
{
return false;
}

/* Initialize queue and push root into it */
queue<Node *> que1;
queue<Node *> que2;

que1.push(root1);
que2.push(root2);

while(!que1.empty() && !que2.empty())
{
Node *temp1 = que1.front();
Node *temp2 = que2.front();

/*
If data of both nodes are same,
then traverse trees further
*/
if(temp1 -> data == temp2 -> data)
{
que1.pop();
que2.pop();

/*
If left child of both tree exists, push it into queue
*/
if(temp1 -> left && temp2 -> left)
{
que1.push(temp1 -> left);
que2.push(temp2 -> left);
}
/*
If left child of only one tree exists, then return false.
*/
else if(temp1 -> left || temp2 -> left)
{
return false;
}

/*
If right child of both tree exists, push it into queue
*/
if(temp1 -> right && temp2 -> right)
{
que1.push(temp1 -> right);
que2.push(temp2 -> right);
}
/*
If right child of only one tree exists, then return false.
*/
else if(temp1 -> right || temp2 -> right)
{
return false;
}
}
/*
If data of both nodes are not same,
then return false
*/
else
{
return false;
}
}
return true;
}

int main()
{
/* Creating a Binary trees and inserting some nodes in it */
Node *root1 = NULL;
Node *root2 = NULL;

root1 = new Node(1);
root1 -> left = new Node(2);
root1 -> right = new Node(3);
root1 -> left -> left = new Node(4);
root1 -> left -> right = new Node(5);
root1 -> right -> left = new Node(6);
root1 -> right -> right = new Node (7);
root1 -> left -> right -> left = new Node(8);
root1 -> right -> left -> right = new Node(9);

root2 = new Node(1);
root2 -> left = new Node(2);
root2 -> right = new Node(3);
root2 -> left -> left = new Node(4);
root2 -> left -> right = new Node(5);
root2 -> right -> left = new Node(6);
root2 -> right -> right = new Node (7);
root2 -> left -> right -> left = new Node(8);
root2 -> right -> left -> right = new Node(9);

/* Calling function to determine if two binary trees are identical or not */
if(checkidentical(root1, root2) == true)
{
cout<<"Given Binary Trees are Identical!!";
}
else
{
cout<<"Given Binary Tree are not Identical!!";
}
}

```

OUTPUT:

`Given Binary Trees are Identical!!`

Related Posts: