# Check if Two Trees are Identical

Problem:
Given two binary trees, write a function to check if they are equal or not.

Solution:
Two binary trees are considered equal if they are structurally identical andthe nodes have the same value.

```public boolean isSameTree(TreeNode p, TreeNode q)
{
if(p==null && q==null)
{
return true;
}
else if(p==null || q==null)
{
return false;
}
else
{
return (p.val == q.val &&
isSameTree(p.left,q.left) &&
isSameTree(p.right,q.right));
}
}
```

Time Complexity: O(N), Where N is number of nodes in a tree.

### 0 Thoughts on “Check if Two Trees are Identical”

1. Simple and elegant recursive solution.
I am loving it

2. bool structurallyEquivalent(node *root1, node *root2) {
if ((root1 && !root2) || (!root1 && root2))
return false;
else if (!root1 && !root2)
return true;
else {
return (structurallyEquivalent(root1->left,root2->left) &&
structurallyEquivalent(root1->right,root2->right));
}
}

bool structurallyEqual(node *root1, node *root2) {
if ((root1 && !root2) || (!root1 && root2))
return false;
else if (!root1 && !root2)
return true;
else if (root1 && root2 && root1->val != root2->val)
return false;
else {
return (structurallyEqual(root1->left,root2->left) &&
structurallyEqual(root1->right,root2->right));
}
}