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.

This article is contributed by Vishwas Garg. You can also contribute by writing and mail it to us: [email protected]

2 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));
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation