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.
This article is contributed by Vishwas Garg. You can also contribute by writing and mail it to us: [email protected].
Simple and elegant recursive solution.
I am loving it
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));
}
}